GA的なもの
何気なく自分の日記を読み返したら、最初のほうに酷い絵を描いてたことを思い出した…
当時どういうテンションだったのこれ…
良くこれで採用して貰えたものです。というわけでコードで埋めてそれっぽいブログにしておこうという試み。
第一から第五希望までの日程をユーザから取得し、ＧＡを使ってシフトを割り当てるというプログラムの一部。
ここだけ抜き出してもしょうがないですが、全文載せるのは色々と支障があるので。
インターンの応募時に提出したもののひとつ。
///
/// 遺伝的アルゴリズムを用いた準最適解の生成
///
public void ga(int O, int MAX_CANDIDATE)
{
double crossOver = 0.9; // 交叉確率
double mutation = 0.6; // 突然変異確率
int population = 200; // 個体群の数
int parentsNum = 50; // 交叉個体数
int rouletteScale = 500; // 親選定時のルーレットサイズ
int eleteNum = 20; // 突然変異を起こさないエリート個体の数
int EvalMax = 10000; // 許容されうる評価値の上限
int M = population / 2;
int generationNumber = 1; // 世代数
closeFlagGA = 0;
this.geneticAlgorithmsTable = new int[population];
geneticEvaluateTable = new double[population];
for (int i = 0; i < population; i++)
{
this.geneticAlgorithmsTable[i] = new int[N]; // N:全組み合わせ数
geneticEvaluateTable[i] = 0;
}
for (int i = 0; i < population; i++)
{
for (int j = 0; j < N; j++)
{
this.geneticAlgorithmsTable[i][j] = j;
}
for (int k = 0; k < N; k++)
{
Random shuffler = new Random(k*i);
int shuffleIndex = shuffler.Next(N);
int h = geneticAlgorithmsTable[i][shuffleIndex];
geneticAlgorithmsTable[i][shuffleIndex] = geneticAlgorithmsTable[i][0];
geneticAlgorithmsTable[i][0] = h;
} // 第1世代の生成。 各遺伝子とも列の回数だけランダムにシャッフルする
}
evalAll = EvalMax;
while(true) // 遺伝的アルゴリズムのメインルーチン
{
geneticEvaluate(population, MAX_CANDIDATE); // 各個体の適応度の評価
int parentsIndex = new int[parentsNum];
parentsIndex = selectGen(population,crossOver,parentsNum,rouletteScale); // 親遺伝子の選択
crossOverGen(population, parentsIndex, crossOver); // 交叉
generationNumber++;
Console.Out.WriteLine("現在の世代：{0}",generationNumber);
mutationGen(population, mutation,eleteNum); // 突然変異
if (closeFlagGA>300) // 収束判定:一定世代で評価値が改善しない場合
{
Console.Out.WriteLine("収束判定ＯＫ");
break;
}
}
}
///
/// 遺伝子評価関数
///
void geneticEvaluate(int population, int MAX_CANDIDATE)
{
int selectedGen = new int[N];
double maxEvaluate = 0.0;
for (int i = 0; i < population ; i++)
{
for (int j = 0 ; j < N ; j++)
{
selectedGen[j] =this.geneticAlgorithmsTable[i][j];
}
if (this.evaluate(selectedGen) > maxEvaluate) maxEvaluate = this.evaluate(selectedGen);
geneticEvaluateTable[i] = this.evaluate(selectedGen);
}
for (int i = 0; i < population; i++)
{
geneticEvaluateTable[i] = maxEvaluate - geneticEvaluateTable[i]; // 評価値を反転させる
}
Array.Sort(geneticEvaluateTable, geneticAlgorithmsTable);
Array.Sort(geneticEvaluateTable);
for (int j = 0; j < N; j++)
{
selectedGen[j] = this.geneticAlgorithmsTable[population -1][j];
}
Console.Out.WriteLine("現在までの最高値:{0}", evalAll);
if (evalAll >= this.evaluate(selectedGen))
{
if (evalAll == this.evaluate(selectedGen))
{
closeFlagGA++;
bool duplicateCheck = true; // 以前に出された解と一致するかを調べる
bool dC = true;
for (int p = 0; p < samePointCandidate; p++)
{
for (int i = 0; i < N; i++)
{
if(storedCandidate[p][i] != selectedGen[i]) dC = false;
}
if(dC) duplicateCheck = false;
}
if (duplicateCheck)
{
for (int p = 0; p < N; p++)
{
this.storedCandidate[samePointCandidate][p] = selectedGen[p];//同点の候補を代入
}
samePointCandidate++;
if (samePointCandidate >= MAX_CANDIDATE)
{
throw new OutOfMemoryException("最大許容解候補数を超えました");
}
}
}
else
{
closeFlagGA = 0;
evalAll = this.evaluate(selectedGen);
try
{
samePointCandidate = 1; //候補数を1個に初期化
for (int p = 0; p < N; p++) //候補の順列を初期化&現在の最良候補を代入
{
for (int q = 1; q < MAX_CANDIDATE; q++)
{
this.storedCandidate[q][p] = 0;
}
this.storedCandidate[0][p] = selectedGen[p];
}
}
catch (Exception E)
{
MessageBox.Show(E.ToString());
}
}
}
}
///
/// 親個体選定関数
///
int selectGen(int population, double crossOver, int parentsnum, double rouletteScale)
{
List parentSelectTable = new List();
Random garand = new System.Random();
double totalEvaluate = 0.0;
for (int i = 0; i < population; i++)
{
totalEvaluate += geneticEvaluateTable[i];
}
for (int i = 0; i < population ;i++ )
{
if *1
{
for (i = overPoint+parentsALength; i < number; i++)
{
children[i] = pb[i - parentsALength];
}
}
return children;
}
///
/// 突然変異生成関数 希望していない日程に入れられた部分に突然変異を強制している
///
void mutationGen(int population,double mutation,int eleteNum)
{
int count = 1;
for (int i = 0; i <( population-eleteNum); i++)
{
if (this.probBool(mutation, i))
{
List overGain = new List();
for (int j = 0; j 1000)
{
overGain.Add(j); // i番目の個体について、ゲイン1000以上の評価値をもつコードを特定する
}
}
Random changeSelecter = new Random(i + count);
Random changeSelecter2 = new Random(i - count);
int point, point2,t;
switch (overGain.Count)
{
case 0:
point = changeSelecter.Next(N);
point2 = changeSelecter2.Next(N);
t = this.geneticAlgorithmsTable[i][point];
this.geneticAlgorithmsTable[i][point] = this.geneticAlgorithmsTable[i][point2];
this.geneticAlgorithmsTable[i][point2] = t;// ランダムで選ばれた点を隣接する点と交換
count++;
break;
case 1:
point = 0;
point2 = changeSelecter2.Next(N);
t = this.geneticAlgorithmsTable[i][overGain[point]];
this.geneticAlgorithmsTable[i][overGain[point]] = this.geneticAlgorithmsTable[i][point2];
this.geneticAlgorithmsTable[i][point2] = t;// ゲイン1000のコードとランダムで選ばれた点を交換
count++;
break;
default:
point = changeSelecter.Next(overGain.Count);
point2 = changeSelecter2.Next(overGain.Count);
t = this.geneticAlgorithmsTable[i][overGain[point]];
this.geneticAlgorithmsTable[i][overGain[point]] = this.geneticAlgorithmsTable[i][overGain[point2]];
this.geneticAlgorithmsTable[i][overGain[point2]] = t;// ゲイン1000のコードどうしを交換
count++;
break;
}
}
}
}
*1:geneticEvaluateTable[i] / 10) >= 1)
{
for (int j = 0; j < (geneticEvaluateTable[i] * rouletteScale / totalEvaluate); j++)
parentSelectTable.Add(i); // 評価値に比例した要素数を各親に割り当てる（ルーレット方式）
}
}
int parentsIndex = new int[parentsnum];
for(int i=0;i
