001package org.opengion.penguin.math; 002 003import java.util.ArrayList; 004import java.util.List; 005import java.util.HashMap; 006import org.apache.commons.math3.genetics.InvalidRepresentationException; 007 008/** 009 * AbstractHybsGAChromosomeのサンプル実装クラスです。 010 * HybsGAObjectImplを利用しています。 011 * 属性値配列(文字列)にタスクの割当先(機械や人)候補 012 * 属性値(実数)にこのタスクにかかる時間 013 * 属性値配列(実数)[0]にこのタスクの納期(開始からの経過時間) 014 * を持たせているという想定です。 015 * このクラスでは次のようにスケジュールを決めます。 016 * 1.候補のうち、一番タスクが積まれていないものに前から積む 017 * 2.同じであればリストの先頭の方に割り当てられる 018 * 3.納期オーバーの場合は評価関数の値が小さくなるようにする 019 * 020 * 021 */ 022public class HybsScheduleChromosome extends AbstractHybsGAChromosome { 023 024 /** 025 * コンストラクタ 026 */ 027 public HybsScheduleChromosome() { 028 super(); 029 } 030 031 /** 032 * コンストラクタ 033 * @param representation 染色体表現 034 */ 035 public HybsScheduleChromosome(final List<HybsGAObject> representation) { 036 super(representation); 037 } 038 039 /** 040 * 適合度計算 041 */ 042 public double fitness() { 043 List<HybsGAObject> representation = getRepresentation(); 044 double nokisum = 0.0; 045 HashMap<String,Double> machineList = new HashMap<String, Double>(); //名前は機械リストだが、人でも良い 046 HashMap<String, ArrayList<String>> taskSchedule = new HashMap<String, ArrayList<String>>(); 047 048 // 実際にスケジュールの積み上げを行い、納期遅れの合計を出します 049 nokisum = makeSchedule( representation, machineList, taskSchedule ); 050 051 052 // リストから最大値を取得する(出てくる順番は問わない) 053 double maxWork=0; 054 for( String mw : machineList.keySet() ){ 055 maxWork = ( machineList.get(mw) > maxWork ) ? machineList.get(mw) :maxWork; 056 } 057 058 return 1 / ( maxWork + nokisum*nokisum); //納期遅れが多くなるとどんどん値が小さくなるように評価する 059 } 060 061 /** 062 * HybsGAObjectImplを利用して前からスケジュールを積み上げていきます。 063 * 064 * @param representation 染色体表現 065 * @param machineList マシンに対する積み上げ工数のリスト。(書き込まれるのでfinalにしない) 066 * @param taskSchedule マシンに対して、前からタスクをセットするリスト。(書き込まれるのでfinalにしない) 067 * @return 納期遅れの累計 068 */ 069 public double makeSchedule( final List<HybsGAObject> representation , HashMap<String,Double> machineList, HashMap<String, ArrayList<String>> taskSchedule){ 070 HybsGAObjectImpl chrom; 071 double nokisum = 0.0; 072 073 for ( int i=0; i<representation.size(); i++){ 074 chrom = (HybsGAObjectImpl)representation.get(i); 075 076 String[] machines = chrom.getAttrStrArray(); 077 // ここでスケジュールを当てはめていく 078 double noki = chrom.getAttrArray()[0]; 079 String hitMachine = null; 080 double work=999999999; 081 for( int j=0; j<machines.length; j++ ){ 082 if(!machineList.containsKey( machines[j] )){ 083 machineList.put( machines[j], new Double(0) ); 084 taskSchedule.put( machines[j], new ArrayList<String>() ); 085 } 086 087 if( machineList.get(machines[j]) < work){ 088 work = machineList.get(machines[j]); 089 hitMachine = machines[j]; 090 } 091 } 092 093 machineList.put( hitMachine, new Double(work + chrom.getAttr()) ); // 総工数 094 taskSchedule.get( hitMachine ).add( chrom.getName() ); // 割りついたタスクリスト 095 096 if( work + chrom.getAttr() > noki ){ 097 nokisum += ( noki - (work + chrom.getAttr()) ); 098 } 099 } 100 return nokisum; 101 } 102 103 /** 104 * 自身のクラスを新たに作成するメソッド。 105 * ここではオプションデータはクローンせずに参照で渡しています。 106 * (計算では利用していません) 107 * 108 * @param repr 染色体表現 109 * @return 作成された自分自身のクラス 110 */ 111 public AbstractHybsGAChromosome newFixedLengthChromosome(final List<HybsGAObject> repr) { 112 HybsScheduleChromosome rtn = new HybsScheduleChromosome(repr); 113 rtn .setOptionData( optionData ); 114 return rtn; 115 } 116 117 /** 118 * 染色体表現のチェック 119 */ 120 protected void checkValidity(List<HybsGAObject> repr) throws InvalidRepresentationException { 121 // Listの中身のチェックをする箇所。必要であれば記述する 122 } 123 124 125}