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