GA的なもの

何気なく自分の日記を読み返したら、最初のほうに酷い絵を描いてたことを思い出した…
当時どういうテンションだったのこれ…
良くこれで採用して貰えたものです。というわけでコードで埋めてそれっぽいブログにしておこうという試み。
第一から第五希望までの日程をユーザから取得し、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("収束判定OK");
                    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 /// 子世代生成関数 /// void crossOverGen(int population, int parentsIndex, double crossOver) { int newGenerationNum = (int)((double)population * crossOver); for (int i = 0; i < newGenerationNum; i++) { Random fatherSelecter = new Random(i); Random motherSelecter = new Random(i*i); // シードを変えることで親の選定にばらつきを持たせる int fatherID = parentsIndex[fatherSelecter.Next(parentsIndex.Length)]; int motherID = parentsIndex[motherSelecter.Next(parentsIndex.Length)]; int father = new int[N]; int mother = new int[N]; for (int j = 0; j < N; j++) { father[j] = this.geneticAlgorithmsTable[fatherID][j]; mother[j] = this.geneticAlgorithmsTable[motherID][j]; } int children = crossOverCalc(father, mother, N, i); for (int k = 0; k < N; k++) { this.geneticAlgorithmsTable[i][k] = children[k]; //上から順に子世代へ置き換える } } } ///

/// 1点交叉関数 /// int crossOverCalc(int parentsA, int parentsB, int number, int seed) { int i; Random crossOverSelecter = new Random(seed); int[] children = new int[number]; List pb = new List(); for(i=0;i

Remove all ads