    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;    // トーナメント個体数：２が一般的
    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}