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 * 内部クラス。 048 * 049 * 突然変異はランダム入れ替え方式とします 050 */ 051// private static class RandomMutation implements MutationPolicy { 052 private static final class RandomMutation implements MutationPolicy { 053 /** 054 * コンストラクタ。 055 * 056 * @param original オリジナル染色体 057 * @return 突然変異染色体 058 */ 059 public Chromosome mutate(final Chromosome original) { 060 final AbstractHybsGAChromosome strChromosome = (AbstractHybsGAChromosome) original; 061 final List<HybsGAObject> lists = strChromosome.getThisRepresentation(); 062 final int mutationIndex1 = GeneticAlgorithm.getRandomGenerator().nextInt(lists.size()); 063 final int mutationIndex2 = GeneticAlgorithm.getRandomGenerator().nextInt(lists.size()); 064 final List<HybsGAObject> mutatedChromosome = new ArrayList<HybsGAObject>(lists); 065 final HybsGAObject mi1 = lists.get(mutationIndex1); 066 final HybsGAObject mi2 = lists.get(mutationIndex2); 067 mutatedChromosome.set(mutationIndex2, mi1); 068 mutatedChromosome.set(mutationIndex1, mi2); 069 return strChromosome.newFixedLengthChromosome(mutatedChromosome); 070 } 071 } 072 073 /** 074 * 計算の実行。 075 * 076 * @return 最適染色体 077 */ 078 public AbstractHybsGAChromosome execute() { 079 // initialize a new genetic algorithm 080 final GeneticAlgorithm ga = new GeneticAlgorithm( 081 new OrderedCrossover<HybsGAObject>(), //CrossoverPolicy:順序交叉を利用する 082 crossoverRate, //crossoverRate 083 new RandomMutation(), //MutationPolicy 084 mutationRate, //mutationRate 085 new TournamentSelection(tournamentArity) //SelectionPolicy 086 ); 087 088 // initial population 089 final Population initial = getInitialPopulation(); 090 091 // stopping condition 092 final StoppingCondition stopCond = new FixedGenerationCount(100); 093 094 // run the algorithm 095 final Population finalPopulation = ga.evolve(initial, stopCond); 096 097 // best chromosome from the final population 098 final Chromosome bestFinal = finalPopulation.getFittestChromosome(); 099 100 return (AbstractHybsGAChromosome)bestFinal; 101 } 102 103 /** 104 * 初期遺伝子の作成。シャッフルする。 105 * 106 * クラスの読み込み部分をfukurouに依存 107 * 108 * @return 初期遺伝子 109 */ 110 private Population getInitialPopulation() { 111 final List<Chromosome> popList = new LinkedList<Chromosome>(); 112 final List<HybsGAObject> gal = Arrays.asList(gaList); 113// AbstractHybsGAChromosome chr = (AbstractHybsGAChromosome)newInstance( chromosomeClazz ); 114 final AbstractHybsGAChromosome chr = (AbstractHybsGAChromosome)SystemUtil.newInstance( chromosomeClazz ); 115 chr.setOptionData( optionData ); 116 for (int i = 0; i < populationSize; i++) { 117 Collections.shuffle(gal); 118 popList.add( chr.clone(gal) ); 119 } 120 return new ElitisticListPopulation(popList, 2 * popList.size(), elitismRate); 121 } 122 123 /** 124 * 染色体配列のセット。 125 * 126 * @param gal 染色体とする配列 127 * @return クラス自身 128 */ 129 public HybsGeneticAlgorithm setGAList(final HybsGAObject[] gal ) { 130 this.gaList = gal; 131 return this; 132 } 133 134 /** 135 * 交叉率のセット。 136 * 交叉率+突然変異率 < 1.0 となるようにする 137 * 初期値は0.8 138 * 139 * @param cr 交叉率 140 * @return クラス自身 141 */ 142 public HybsGeneticAlgorithm setCrossoverRate(final double cr ){ 143 this.crossoverRate = cr; 144 return this; 145 } 146 147 /** 148 * 突然変異率のセット。 149 * 交叉率+突然変異率 < 1.0 となるようにする 150 * 初期値は0.05 151 * 152 * @param mr 突然変異率 153 * @return クラス自身 154 */ 155 public HybsGeneticAlgorithm setMutationRate(final double mr ){ 156 this.mutationRate = mr; 157 return this; 158 } 159 160 /** 161 * エリート主義の割合。 162 * 初期値は0.2 163 * 164 * @param er エリート主義の率 165 * @return クラス自身 166 */ 167 public HybsGeneticAlgorithm setElitismRate(final double er ){ 168 this.elitismRate = er; 169 return this; 170 } 171 172 /** 173 * トーナメントサイズ。 174 * 初期値は2 175 * 176 * @param ta トーナメントサイズ 177 * @return クラス自身 178 */ 179 public HybsGeneticAlgorithm setTournamentArity(final int ta ){ 180 this.tournamentArity = ta; 181 return this; 182 } 183 184 /** 185 * 集団サイズ。 186 * 染色体のサイズ等によって適度な値を取るべきだが、初期値は100としている。 187 * 188 * 189 * @param ps 集団サイズ 190 * @return クラス自身 191 */ 192 public HybsGeneticAlgorithm setPopulationSize(final int ps ){ 193 this.populationSize = ps; 194 return this; 195 } 196 197 /** 198 * 利用する染色体クラスを指定します。 199 * 初期値はorg.opengion.fukurou.math.HybsScheduleChromosome 200 * 201 * @param cc 染色体のクラス名 202 * @return クラス自身 203 */ 204 public HybsGeneticAlgorithm setChromosomeClazz(final String cc ){ 205 this.chromosomeClazz = cc; 206 return this; 207 } 208 209 /** 210 * 染色体クラスにオプションをセットします。 211 * 212 * @param obj オプションデータ 213 * @return クラス自身 214 */ 215 public HybsGeneticAlgorithm setOptionData(final Object obj ){ 216 this.optionData = obj; 217 return this; 218 } 219 220 /*** ここまでがGA本体 ***/ 221 /** 222 * ここからテスト用mainメソッド。 223 * 224 * @param args **************************************** 225 */ 226 public static void main(final String [] args) { 227 228 final AbstractHybsGAChromosome rtn1 = new HybsGeneticAlgorithm() 229 .setChromosomeClazz("org.opengion.penguin.math.HybsTSPChromosome") 230 .setGAList(new HybsGAObject[] { 231 new HybsGAObjectImpl("1",1,new double[] {1,1}) 232 ,new HybsGAObjectImpl("2",2,new double[] {1,10}) 233 ,new HybsGAObjectImpl("3",3,new double[] {11,20}) 234 ,new HybsGAObjectImpl("4",4,new double[] {22,50}) 235 ,new HybsGAObjectImpl("5",5,new double[] {25,70}) 236 ,new HybsGAObjectImpl("6",6,new double[] {33,5}) 237 ,new HybsGAObjectImpl("7",7,new double[] {54,20}) 238 ,new HybsGAObjectImpl("8",8,new double[] {75,80}) 239 ,new HybsGAObjectImpl("9",9,new double[] {86,55}) 240 ,new HybsGAObjectImpl("10",10,new double[] {97,90}) 241 ,new HybsGAObjectImpl("11",11,new double[] {18,50}) 242 ,new HybsGAObjectImpl("12",12,new double[] {39,10}) 243 ,new HybsGAObjectImpl("13",13,new double[] {40,90}) 244 ,new HybsGAObjectImpl("14",14,new double[] {51,10}) 245 ,new HybsGAObjectImpl("15",15,new double[] {62,55}) 246 ,new HybsGAObjectImpl("16",16,new double[] {73,70}) 247 ,new HybsGAObjectImpl("17",17,new double[] {84,10}) 248 ,new HybsGAObjectImpl("18",18,new double[] {95,45}) 249 }).execute(); 250 251 System.out.println(rtn1.toString()); 252 System.out.println( 1/rtn1.getFitness() +"\n"); 253 } 254}