LoginSignup
6
7

More than 3 years have passed since last update.

@AmefuriTell(てる* あめふり)

C++で遺伝的アルゴリズムを使ってナップザック問題を解いた話

Posted at

0. 初めのあいさつ

1. 自己紹介

しがない大学生のあめふりてる*と申します。主に、HSP3と補助としてC/C++を使用しています。
競技プログラミングをほんの少しだけ嗜んでいましたが、最近はコンテストに出れてないので嗜んでいません。

2. 今回の記事を書く経緯

最近、遺伝的アルゴリズムにはまっていたところで、こちらのツイートを見て「よっしゃ。解いたるわ！」という感じでやってみた記録を残しておこうと思い筆をとりました。

1. OneMax問題

さてここで、OneMax問題を解いていこうと思います。
なぜそれをするかというと、本題である「ナップザック問題」は、この「OneMax問題」のある一部分を書き換えるだけで解くことができるからです。それについては、この記事を読み終わるころには分かると思います。
「早く本題が見たい」という方は飛ばしてもらって構いません。

1. OneMax問題とは

OneMax問題とは何かというと、0と1のみからなる数列の和を最大化する問題のことです。言い換えると、数列の各要素が1にする問題のことです。
0と1からなる数列とは、例えば、[0, 1, 1, 0, 1]のような数列です。これを[1, 1, 1, 1, 1]にするのが最終目標です。
これを遺伝的アルゴリズムで解いていきましょう。

なお遺伝的アルゴリズムについては、以前私の書いた記事、「HSP3で遺伝的アルゴリズムをした話 〜遺伝的アルゴリズムの概略と「ムダにクリエイティブ」な"Hello,World!"〜」に遺伝的アルゴリズムとOneMax問題についてのざっくりとした内容は書いたのでこちらを参照してください。特に、OneMax問題に関しては、こちらで書いた記事のコードをC++に変換しただけなのでコードの説明も省かせていただきます。

2. コード

OneMax問題.cpp
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

typedef struct {
    double score;
    vector<int> gen;
}biont;

int ScoreCalc(vector<int> &gen)//評価関数
{
    int score = 0;
    for (int i = 0; i < (int)gen.size(); i++)
    {
        score += gen[i];
    }
    return score;
}

bool ComparisonFunction(const biont &a, const biont &b)//比較関数
{
    return a.score > b.score;
}

int main()
{
    srand((unsigned)time(NULL));
    //変数初期化
        int len = 100;
        int biont_number = 100;
        int parents_number = biont_number / 2;
        int generation = 1000;

        vector<biont> parents(len);
        vector<biont> childlen(len);

        for (int i = 0; i < biont_number; i++)
        {
            parents[i].gen.resize(len);
            childlen[i].gen.resize(len);
        }

    //初期遺伝子生成
        for (int i = 0; i < biont_number; i++)
        {
            for (int j = 0; j < len; j++)
            {
                parents[i].gen[i] = 0;
            }
        }
    //メイン
        while (generation--)
        {
            //スコア計算
                for (int i = 0; i < biont_number; i++)
                {
                    parents[i].score = ScoreCalc(parents[i].gen);
                }
            //ソート
                sort(parents.begin(), parents.end(), ComparisonFunction);
            /*/一番優れたものを表示
                for (int j = 0; j < biont_number; j++)
                {
                    cout << parents[j].score << " ";
                    for (int i = 0; i < len; i++)
                    {
                        cout << parents[j].gen[i];
                    }
                    cout << endl;
                }*/
            //交叉
                //優れた親を保存
                    for (int i = 0; i < parents_number; i++)
                    {
                        childlen[i].gen = parents[i].gen;
                    }
                //優れた親から子を生成
                    for (int i = parents_number; i < biont_number; i += 2)
                    {

                        //二点交叉
                            int p_i = i - parents_number;
                            childlen[i].gen = parents[p_i].gen;
                            childlen[i + 1].gen = parents[p_i + 1].gen;

                            int left = rand() % len, right = rand() % len;
                            if(left > right)swap(left, right);

                            for (int j = left; j <= right; j++)
                            {
                                childlen[i].gen[j] = parents[p_i + 1].gen[j];
                                childlen[i + 1].gen[j] = parents[p_i].gen[j];
                            }
                    }
            //突然変異
                for (int i = parents_number; i < biont_number; i++)
                {
                    for (int j = 0; j < len; j++)
                    {
                        if(rand() % len == 0)
                        {
                            if(childlen[i].gen[j] == 0)
                            {
                                childlen[i].gen[j] = 1;
                            }
                            else
                            {
                                childlen[i].gen[j] = 0;
                            }
                        }
                    }
                }
            //世代交代
                for (int i = 0; i < biont_number; i++)
                {
                    parents[i].gen = childlen[i].gen;
                }
        }
    //最終スコア
    cout << parents[0].score << " ";
    for (int i = 0; i < len; i++)
    {
        cout << parents[0].gen[i];
    }
}

以上がOnaMax問題でした。HSP3で書くよりも楽に書くことができます。HSP3erとしては少し悲しいです。

2. ナップザック問題

さて、いよいよ本題に移っていきたいと思います。先ほども言いましたが、OneMax問題のコードを書き換えることでナップザック問題を解かすプログラムになります。

1. ナップザック問題とは

まず、ナップザック問題とは何かについて説明します。
ナップザック問題とは、「ある容量のナップザックに、容量を超えないようにいくつかの品物を詰め込むとき、詰め込んだ品物の価値が最大化するためにはどの品物を入れればよいか」という問題で、いわゆる整数計画問題で、すべての可能性を検証するにはとてつもない時間がかかるため難しい問題です。

競技プログラミングをする人なら「動的計画法」を使ってあっさり解いてしまいますが、今回は遺伝的アルゴリズムを使って解いていきます。

2. コード

早速コードを見ていきます。が、基本的にはOneMax問題と変わりません。変わったのは「評価関数」の部分です。そこをコードを見ながら確認していきましょう。なお、今回のコードは、こちらの問題を解くコードとなっています。入力形式に関しては、そちらを参照してください。遺伝的アルゴリズムを使用する手前、どうしても本当にそれが最大かどうかが分かりません。そこが遺伝的アルゴリズムの弱点であるといえます。

以下コードです。

ナップザック問題.cpp
#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

typedef struct
{
    double score;
    vector<int> gen;
}biont;

int ScoreCalc(vector<int> &gen, int w_limit, vector<int> &v, vector<int> &w)//評価関数
{
    int value = 0, wight = 0;
    for (int i = 0; i < (int)gen.size(); i++)
    {
        if(gen[i] == 1)
        {
            value += v[i];
            wight += w[i];
        }
    }
    if(wight > w_limit)return 0;
    else return value;
}

bool ComparisonFunction(const biont &a, const biont &b)//比較関数
{
    return a.score > b.score;
}

int main()
{
    srand((unsigned)time(NULL));
    //入力
        int N, W;
        cin >> N >> W;

        vector<int> v(N), w(N);
        for (int i = 0; i < N; i++)
        {
            cin >> v[i] >> w[i];
        }

    //変数初期化
        int len = N;
        int biont_number = 128;
        int parents_number = biont_number / 2;
        int generation = 10000;

        vector<biont> parents(biont_number);
        vector<biont> childlen(biont_number);

    //初期遺伝子生成
        for (int i = 0; i < biont_number; i++)
        {
            for (int j = 0; j < len; j++)
            {
                parents[i].gen.push_back(rand() % 2);
            }
        }
    //メイン
        while (generation--)
        {
            //スコア計算
                for (int i = 0; i < biont_number; i++)
                {
                    parents[i].score = ScoreCalc(parents[i].gen, W, v, w);
                }
            //ソート
                sort(parents.begin(), parents.end(), ComparisonFunction);
            /*/一番優れたものを表示
                for (int j = 0; j < biont_number; j++)
                {
                    cout << parents[j].score << " ";
                    for (int i = 0; i < len; i++)
                    {
                        cout << parents[j].gen[i];
                    }
                    cout << endl;
                }
            *///交叉
                //優れた親を保存
                    for (int i = 0; i < parents_number; i++)
                    {
                        childlen[i].gen = parents[i].gen;
                    }
                //優れた親から子を生成
                    for (int i = parents_number; i < biont_number; i += 2)
                    {

                        //二点交叉
                            int p_i = i - parents_number;
                            childlen[i].gen = parents[p_i].gen;
                            childlen[i + 1].gen = parents[p_i + 1].gen;

                            int left = rand() % len, right = rand() % len;
                            if(left > right)swap(left, right);

                            for (int j = left; j <= right; j++)
                            {
                                childlen[i].gen[j] = parents[p_i + 1].gen[j];
                                childlen[i + 1].gen[j] = parents[p_i].gen[j];
                            }
                    }
            //突然変異
                for (int i = parents_number; i < biont_number; i++)
                {
                    for (int j = 0; j < len; j++)
                    {
                        if(rand() % len == 0)
                        {
                            if(childlen[i].gen[j] == 0)
                            {
                                childlen[i].gen[j] = 1;
                            }
                            else
                            {
                                childlen[i].gen[j] = 0;
                            }
                        }
                    }
                }
            //世代交代
                for (int i = 0; i < biont_number; i++)
                {
                    parents[i].gen = childlen[i].gen;
                }
        }
    //最終スコア
    cout << parents[0].score << endl;
}

こんなコードになります。評価関数のみが変わったことに気づいたでしょうか？
その評価関数について次項で見ていきます。

3. 評価関数の変更点

さて、評価関数を見ていきましょう。

int ScoreCalc(vector<int> &gen, int w_limit, vector<int> &v, vector<int> &w)//評価関数
{
    int value = 0, wight = 0;
    for (int i = 0; i < (int)gen.size(); i++)
    {
        if(gen[i] == 1)
        {
            value += v[i];
            wight += w[i];
        }
    }
    if(wight > w_limit)return 0;
    else return value;
}

評価関数を説明するとこうです。

genが1の時にナップザックに品物をいれていき、品物の重さの合計がナップザックの限界を超えていたら 0 を出力します。
逆に超えていなければ、品物の価値を出力します。

要するに、bit全探索のような感じになっているわけですね。大きな変更はこれだけです。
これだけで、OneMax問題から全く別のナップザック問題が解けるというのはなかなか面白いですよね。

3. 最後の挨拶

ここまで読んでいただきありがとうございました。この記事を書こう！と思って1時間で仕上げたものなので至らない点などありましたら、コメントいただけたら幸いです。
質問も受け付けております。

良かったらいいねください。
また、機会があればぜひ私の記事を読んでいただけたら嬉しいです。ではでは、お相手はあめふりてる*でした。

6
7
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
7