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