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