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}