001package org.opengion.penguin.math; 002 003import java.util.Collections; 004import java.util.List; 005import java.util.Arrays; 006import java.util.LinkedList; 007import java.util.ArrayList; 008import org.apache.commons.math3.genetics.MutationPolicy; 009import org.apache.commons.math3.genetics.Chromosome; 010import org.apache.commons.math3.genetics.ElitisticListPopulation; 011import org.apache.commons.math3.genetics.FixedGenerationCount; 012import org.apache.commons.math3.genetics.GeneticAlgorithm; 013import org.apache.commons.math3.genetics.OrderedCrossover; 014import org.apache.commons.math3.genetics.Population; 015import org.apache.commons.math3.genetics.StoppingCondition; 016import org.apache.commons.math3.genetics.TournamentSelection; 017import org.opengion.penguin.common.SystemUtil; 018 019/** 020 * apache.commons.mathを利用した遺伝的アルゴリズム実行クラスです。 021 * 0/1ではなくリスト形式の染色体をある程度手軽に利用できるようにしています。 022 * 利用する場合は上記パッケージをjava\jre\lib\ext等に配置してください。 023 * 024 * 交叉率等はsetterで与えられるようにしています。 025 * スケジューリング等を考慮して、交叉方法はOrderedCrossover(順序交叉)としています。 026 * 選択方式はトーナメントです。突然変異は遺伝子ランダム入れ替えです。 027 * 028 * 染色体として与えるものはhybsGAObjectインタフェイスを継承したクラスです。 029 * AbstractListChromosomeを継承したAbstracthybsChromosomeを利用して染色体を作成します。 030 * 031 * 032 * mainメソッドではサンプルとして、巡回セールスマン問題を行います。 033 */ 034public class HybsGeneticAlgorithm { 035 // 標準設定 036 private int populationSize = 100; // 個数 037 private double crossoverRate = 0.8; // 交叉率 038 private double mutationRate = 0.05; // 突然変異率 039 private double elitismRate = 0.1; // 残すエリートの割合 040 private int tournamentArity = 2; // トーナメント個体数:2が一般的 041 private String chromosomeClazz = "org.opengion.fukurou.math.HybsScheduleChromosome"; // 利用する染色体 042 private Object optionData; // 作成する染色体クラスに自由にオプション情報を渡せるようにしておく 043 044 private HybsGAObject [] gaList; 045 046 // 突然変異はランダム入れ替え方式とします 047 private static class RandomMutation implements MutationPolicy { 048 public Chromosome mutate(Chromosome original) { 049 AbstractHybsGAChromosome strChromosome = (AbstractHybsGAChromosome) original; 050 List<HybsGAObject> lists = strChromosome.getThisRepresentation(); 051 int mutationIndex1 = GeneticAlgorithm.getRandomGenerator().nextInt(lists.size()); 052 int mutationIndex2 = GeneticAlgorithm.getRandomGenerator().nextInt(lists.size()); 053 List<HybsGAObject> mutatedChromosome = new ArrayList<HybsGAObject>(lists); 054 HybsGAObject mi1 = lists.get(mutationIndex1); 055 HybsGAObject mi2 = lists.get(mutationIndex2); 056 mutatedChromosome.set(mutationIndex2, mi1); 057 mutatedChromosome.set(mutationIndex1, mi2); 058 return strChromosome.newFixedLengthChromosome(mutatedChromosome); 059 } 060 } 061 062 063 /** 064 * 計算の実行 065 * 066 * @return 最適染色体 067 */ 068 public AbstractHybsGAChromosome execute() { 069 // initialize a new genetic algorithm 070 GeneticAlgorithm ga = new GeneticAlgorithm( 071 new OrderedCrossover<HybsGAObject>(), //CrossoverPolicy:順序交叉を利用する 072 crossoverRate, //crossoverRate 073 new RandomMutation(), //MutationPolicy 074 mutationRate, //mutationRate 075 new TournamentSelection(tournamentArity) //SelectionPolicy 076 ); 077 078 // initial population 079 Population initial = getInitialPopulation(); 080 081 // stopping condition 082 StoppingCondition stopCond = new FixedGenerationCount(100); 083 084 // run the algorithm 085 Population finalPopulation = ga.evolve(initial, stopCond); 086 087 // best chromosome from the final population 088 Chromosome bestFinal = finalPopulation.getFittestChromosome(); 089 090 return (AbstractHybsGAChromosome)bestFinal; 091 } 092 093 // 初期遺伝子の作成。シャッフルする。 094 // クラスの読み込み部分をfukurouに依存 095 private Population getInitialPopulation() { 096 List<Chromosome> popList = new LinkedList<Chromosome>(); 097 List<HybsGAObject> gal = Arrays.asList(gaList); 098// AbstractHybsGAChromosome chr = (AbstractHybsGAChromosome)newInstance( chromosomeClazz ); 099 AbstractHybsGAChromosome chr = (AbstractHybsGAChromosome)SystemUtil.newInstance( chromosomeClazz ); 100 chr.setOptionData( optionData ); 101 for (int i = 0; i < populationSize; i++) { 102 Collections.shuffle(gal); 103 popList.add( chr.clone(gal) ); 104 } 105 return new ElitisticListPopulation(popList, 2 * popList.size(), elitismRate); 106 } 107 108 /** 109 * 染色体配列のセット 110 * 111 * @param gal 染色体とする配列 112 * @return クラス自身 113 */ 114 public HybsGeneticAlgorithm setGAList(final HybsGAObject[] gal ) { 115 this.gaList = gal; 116 return this; 117 } 118 119 120 /** 121 * 交叉率のセット 122 * 交叉率+突然変異率 < 1.0 となるようにする 123 * 初期値は0.8 124 * 125 * @param cr 交叉率 126 * @return クラス自身 127 */ 128 public HybsGeneticAlgorithm setCrossoverRate(final double cr ){ 129 this.crossoverRate = cr; 130 return this; 131 } 132 133 /** 134 * 突然変異率のセット 135 * 交叉率+突然変異率 < 1.0 となるようにする 136 * 初期値は0.05 137 * 138 * @param mr 突然変異率 139 * @return クラス自身 140 */ 141 public HybsGeneticAlgorithm setMutationRate(final double mr ){ 142 this.mutationRate = mr; 143 return this; 144 } 145 146 /** 147 * エリート主義の割合 148 * 初期値は0.2 149 * 150 * @param er エリート主義の率 151 * @return クラス自身 152 */ 153 public HybsGeneticAlgorithm setElitismRate(final double er ){ 154 this.elitismRate = er; 155 return this; 156 } 157 158 /** 159 * トーナメントサイズ 160 * 初期値は2 161 * 162 * @param ta トーナメントサイズ 163 * @return クラス自身 164 */ 165 public HybsGeneticAlgorithm setTournamentArity(final int ta ){ 166 this.tournamentArity = ta; 167 return this; 168 } 169 170 /** 171 * 集団サイズ 172 * 染色体のサイズ等によって適度な値を取るべきだが、初期値は100としている。 173 * 174 * 175 * @param ps 集団サイズ 176 * @return クラス自身 177 */ 178 public HybsGeneticAlgorithm setPopulationSize(final int ps ){ 179 this.populationSize = ps; 180 return this; 181 } 182 183 /** 184 * 利用する染色体クラスを指定します。 185 * 初期値はorg.opengion.fukurou.math.HybsScheduleChromosome 186 * 187 * @param cc 染色体のクラス名 188 * @return クラス自身 189 */ 190 public HybsGeneticAlgorithm setChromosomeClazz(final String cc ){ 191 this.chromosomeClazz = cc; 192 return this; 193 } 194 195 /** 196 * 染色体クラスにオプションをセットします 197 * 198 * @param obj オプションデータ 199 * @return クラス自身 200 */ 201 public HybsGeneticAlgorithm setOptionData(final Object obj ){ 202 this.optionData = obj; 203 return this; 204 } 205 206 207 /*** ここまでがGA本体 ***/ 208 /*** ここからテスト用mainメソッド ***/ 209 /** 210 * @param args *****************************************/ 211 public static void main(final String [] args) { 212 213 AbstractHybsGAChromosome rtn1 = new HybsGeneticAlgorithm() 214 .setChromosomeClazz("org.opengion.penguin.math.HybsTSPChromosome") 215 .setGAList(new HybsGAObject[] { 216 new HybsGAObjectImpl("1",1,new double[] {1,1}) 217 ,new HybsGAObjectImpl("2",2,new double[] {1,10}) 218 ,new HybsGAObjectImpl("3",3,new double[] {11,20}) 219 ,new HybsGAObjectImpl("4",4,new double[] {22,50}) 220 ,new HybsGAObjectImpl("5",5,new double[] {25,70}) 221 ,new HybsGAObjectImpl("6",6,new double[] {33,5}) 222 ,new HybsGAObjectImpl("7",7,new double[] {54,20}) 223 ,new HybsGAObjectImpl("8",8,new double[] {75,80}) 224 ,new HybsGAObjectImpl("9",9,new double[] {86,55}) 225 ,new HybsGAObjectImpl("10",10,new double[] {97,90}) 226 ,new HybsGAObjectImpl("11",11,new double[] {18,50}) 227 ,new HybsGAObjectImpl("12",12,new double[] {39,10}) 228 ,new HybsGAObjectImpl("13",13,new double[] {40,90}) 229 ,new HybsGAObjectImpl("14",14,new double[] {51,10}) 230 ,new HybsGAObjectImpl("15",15,new double[] {62,55}) 231 ,new HybsGAObjectImpl("16",16,new double[] {73,70}) 232 ,new HybsGAObjectImpl("17",17,new double[] {84,10}) 233 ,new HybsGAObjectImpl("18",18,new double[] {95,45}) 234 }).execute(); 235 236 System.out.println(rtn1.toString()); 237 System.out.println( 1/rtn1.getFitness() +"\n"); 238 } 239} 240