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}