【C#プログラミング】遺伝的アルゴリズムを実装してみた（NSGA2）

はじめに

私は研究でC#を扱っています。遺伝的アルゴリズムも扱っており、そのランキング付けの一つであるNSGA2を実装したのでコードを貼りたいと思います！
もし、C#を用いて遺伝的アルゴリズムや最適化手法を検討している人がいれば参考にしてもらえると幸いです！

遺伝的アルゴリズム（GA）とは？

遺伝的アルゴリズムとは生物の進化の仕組みを模した確率的多点探索法です。最適化手法の1つとしてもしかしたら有名かも？です。
生物の進化の過程で「環境適応度の高い個体が生き残り、弱い個体は自然淘汰される」という現象を利用しています。

NSGA2とは？

多目的最適化手法の1つです。簡単に言うと「環境適応度の高い個体＝複数の評価関数で良い評価を得たもの」としている方法です。最適化に詳しい人ならばパレートフロントと呼んだ方が理解できるかもしれませんね。

実際に書いたコード

    /// <summary>
    /// NSGA2による並び替え
    /// </summary>
    private void SortByNSGA2()
    {
      List<List<Individual>> _fronts = new List<List<Individual>>();
      CheckDominationRelation();
      RankSort(_fronts);
      CalDistance(_fronts);
      RankingSort(_fronts);
    }

    /// <summary>
    /// 各個体同士の支配関係を調べる．
    /// </summary>
    private void CheckDominationRelation()
    {
      paretoIndis.Clear();
      List<Individual> _individuals = new List<Individual>(individuals.ToList());
      foreach (Individual _individual in _individuals) _individual.IsNewSolution = true;
      foreach (Individual _targetIndi in _individuals)
      {
        _targetIndi.Rank = 0;
        _targetIndi.DominateCount = 0;
        _targetIndi.DominatedIndis = new List<Individual>();

        foreach (Individual _compareIndi in _individuals)
        {
          if (_targetIndi == _compareIndi) continue;

          //_targetIndiが_compareIndiに対して支配関係にあるかどうかを調べている．
          //そのために，各評価関数でカウントを行っている．
          int _dominateFunc = 0, _sameFunc = 0, _dominatedFunc = 0;
          for (int _funci = 0; _funci < PARETO_FUNCMAX; _funci++)
          {
            if (_compareIndi.Fitnesses[_funci] < _targetIndi.Fitnesses[_funci]) _dominateFunc++;
            else if (_compareIndi.Fitnesses[_funci] == _targetIndi.Fitnesses[_funci]) _sameFunc++;
            else _dominatedFunc++;
          }
          if (_dominateFunc == PARETO_FUNCMAX)
            _targetIndi.DominateCount++;
          else if (_dominatedFunc == PARETO_FUNCMAX)
            _targetIndi.DominatedIndis.Add(_compareIndi);
          else if (_sameFunc == PARETO_FUNCMAX && _targetIndi.IsNewSolution)
            _compareIndi.IsNewSolution = false;
        }

        //何も支配していないならば，ランクは1
        if (_targetIndi.DominateCount == 0)
        {
          _targetIndi.Rank = 1;

          //重複解なしパレートフロントならば残しておく．
          //交叉させないようにするため．
          if (_targetIndi.IsNewSolution) paretoIndis.Add(_targetIndi);
        }
      }
    }

    /// <summary>
    /// ランク付けを行う．
    /// </summary>
    private void RankSort(List<List<Individual>> _fronts)
    {
      int _curRank = 1;
      List<Individual> _curFront = individuals.Where(_indi => _indi.Rank == _curRank).ToList();

      //パレートフロントが無くなるまで続ける．
      while (_curFront.Any())
      {
        List<Individual> _nextFront = new List<Individual>();

        //ランク付けが終わった個体をなくして考える．
        foreach (Individual _rankedIndi in _curFront)
        {
          foreach (Individual _dominateIndi in _rankedIndi.DominatedIndis)
          {
            _dominateIndi.DominateCount--;
            if (_dominateIndi.DominateCount == 0)
            {
              _dominateIndi.Rank = _curRank + 1;
              _nextFront.Add(_dominateIndi);
            }
          }
        }
        _fronts.Add(_curFront);
        _curFront = _nextFront;
        _curRank++;
      }
    }

    /// <summary>
    /// 同ランク内で距離計算を行う．
    /// </summary>
    private void CalDistance(List<List<Individual>> _fronts)
    {
      foreach (List<Individual> _curFront in _fronts)
      {
        foreach (Individual _frontIndi in _curFront) _frontIndi.Distance = 0;

        for (int _funci = 0; _funci < FUNC_MAX; _funci++)
        {
          List<Individual> _sorted = _curFront
                .Where(_indi => _indi.IsNewSolution)
                .OrderBy(_indi => _indi.Fitnesses[_funci])
                .ToList();

          _sorted.First().Distance = double.MaxValue / (FUNC_MAX + 1);
          _sorted.Last().Distance = double.MaxValue / (FUNC_MAX + 1);

          double _minObj = _sorted.First().Fitnesses[_funci];
          double _maxObj = _sorted.Last().Fitnesses[_funci]; ;
          double _range = _maxObj - _minObj;

          for (int _indii = 1; _indii < _sorted.Count - 1; _indii++)
          {
            _sorted[_indii].Distance += _sorted[_indii + 1].Fitnesses[_funci] - _sorted[_indii - 1].Fitnesses[_funci];
            _sorted[_indii].Distance /= _range;
          }
        }
      }
    }

    /// <summary>
    /// ランキング付けを行う．
    /// 距離が大きいものから順番に行う．
    /// </summary>
    private void RankingSort(List<List<Individual>> _fronts)
    {
      //1位個体だけは任意の評価関数でランキング付けをする．
      int _ranking = 0;
      bestIndividual = UTIL.DictionarySort(_fronts[0].ToArray(), 1).First();
      bestIndividual.Ranking = _ranking;
      rankingedIndis[_ranking] = bestIndividual;
      _ranking++;
      _fronts[0].Remove(bestIndividual);

      foreach (List<Individual> _nowFronts in _fronts)
      {
        _nowFronts.OrderByDescending(_indi => _indi.Distance).ToList();
        foreach (Individual _individual in _nowFronts)
        {
          _individual.Ranking = _ranking;
          rankingedIndis[_ranking] = _individual;
          _ranking++;
        }
      }
    }

以上です！ありがとうございました！