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