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