遺伝的アルゴリズム(GA)でナップサック問題を解いてみた

こんにちは、すけと申します。

単目的ナップサック問題を遺伝的アルゴリズム(以下GA)で解くサンプルプログラムをPythonで作成しましたので、解説していきます。Pythonがわからない方、遺伝的アルゴリズムがわからない方にも読んでいただけるよう、わかりやすく説明しますので、どうかお付き合いください。サンプルプログラムを見れば、GAだけでなく、Pythonの勉強にもなると思います。

なぜPythonを選んだかというと、最近人気のある言語なので多くの方に見てもらえるかなぁと考えたためです。ただそれだけの理由です。

ナップサック問題と、遺伝的アルゴリズムについてはブログの記事にまとめましたので、こちらをご覧ください。

ナップザック問題とは？
遺伝的アルゴリズムとは？

今回使用するナップサック問題のアイテム情報は、下記のスプレッドシートに記載しました。もし使用したい方がおりましたらご自由にどうぞ。

ナップサック問題のアイテムCSVファイル

ソースコードの説明では行数を用いて説明しておりますが、Qiitaでは行数が表示されないためわかりづらいかと思います。下記のブログに同じ内容の記事を載せておりますので、行数があったほうがわかりやすいという方はブログの記事をご覧ください。

遺伝的アルゴリズム(GA)でナップサック問題を解いてみた(1)

クラス構成

サンプルプログラムは、下記のクラスで構成されています。クラスごとに順に中身を説明していきます。

• Individual.py: 個体クラス


• InputCsv.py: CSVファイル読み込みクラス


• Item.py: アイテムクラス


• Main.py: メインクラス


• OutputCsv.py: CSVファイル出力クラス


• Parameter.py: パラメータクラス


• Population.py: 母集団クラス


• Util.py: ユーティリティクラス

CSVファイルの読み込み

まず、ナップサック問題のアイテムの情報を、CSVファイルから読み込む部分を作成してしまいます。
しばらくPythonの説明になるかと思いますが、ご了承ください。

下記のInputCsv.pyは、アイテム情報が記載されたCSVファイルを読み込むためのクラスです。
この辺のプログラムは、私がPythonにそんなに慣れていないこともあり、もっとスマートに設計したり、書けたりできるかもしれません。

なるべくコメントを(自分のためにも)詳細に書くようにしておりますので、コメントも理解するヒントになるかと思います。

まず読み込むCSVファイルの構成について説明しておきます。CSVファイルの構成は下記のようになっております。

• 1列目: アイテムの価値


• 2列目: アイテムの重さ

1行が1つのアイテムに対応しており、今回は20個のアイテムがあるため、CSVファイルのアイテム情報は20行あることになります。

InputCsv.py

# -*- coding: utf-8 -*-

import os.path
import Parameter
import csv

# CSVファイル読み込みクラス
class InputCsv:
    def __init__(self, file_name):
        self.file_name = file_name    # 入力ファイル名
        self.input_str = []           # 読み込みバッファ

    # file_nameファイルをバッファに読み込む
    def read(self):

        if not os.path.isfile(self.file_name):
            print("[エラー]:" + str(self.file_name) + "がありません")
            return False

        f = open(self.file_name, 'r')
        csv_in = csv.reader(f)
        self.input_str = [row for row in csv_in]

        f.close

        return True

1行目は文字コードをUTF-8に設定しています。これを書かないでコメントに日本語文字を使うと、エラーが生じます。

8〜11行目はコンストラクタです。このInputCsvクラスは、file_name(入力ファイル名)、input_str(読み込んだ文字列を格納しておくバッファ)を持ちます。インスタンス生成時には、入力ファイル名(アイテム情報が書かれたCSVファイル)を引数で渡します。

14行目のreadメソッドで、CSVファイルの中身を読み込んでいきます。
16〜18行目で念のため、CSVファイルが存在するかチェックしています。もしファイルが存在しない場合は、メッセージを出力してFalseを返します。これは呼び出し側のMainプログラムで戻り値をチェックし、Falseであった場合は、プログラムを終了させるようにするためです。

20〜22行目でCSVファイルをオープンし、データをinput_str変数に格納します。input_str変数には、読み込み元のCSVファイルのように、二次元配列が格納されます。

24行目でファイルをクローズし、26行目で読み込み成功を示すTrueを戻り値で返します。

このInputCsvクラスは、CSVファイルを読み込むような他のプログラムでも使用できるため、再利用性が高いです。

アイテムクラスの作成

Item.pyは、ナップサックに入れるアイテムを表すクラスです。

Item.py

 # -*- coding: utf-8 -*-

 # アイテムクラス
class Item:
    items_list = []      # アイテムのリスト

    def __init__(self, value, weight):
        self.value  = value     # 価値
        self.weight = weight    # 重さ

    @staticmethod
    # アイテムの情報を初期化する
    # 引数は読み取ったcsvデータが格納された2次元配列
    def init_items(read_buffer):

        # 最初の行は項目名なので除外する
        read_buffer.pop(0)

        # items_listにアイテムインスタンスを格納していく
        for pair in read_buffer:
            item = Item(int(pair[0]), int(pair[1]))
            Item.items_list.append(item)

Itemクラスは、value(価値)とweight(重さ)をインスタンス変数として持ちます(8、9行目)。valueとweightの値は、Itemクラスのインスタンス生成時に引数で受け取ります。

14行目のinit_itemsメソッドは、先ほどInputCsvクラスで読み込んだアイテムの情報を使用して、アイテムたちを初期化していきます。
CSVファイルの1行目はアイテムの値ではなく、項目名が書かれているので、17行目で1行目を除外しています。

引数(read_buffer)として、二次元配列(InputCsvクラスのinput_str変数)を受け取ります。
pair[0]とpair[1]がそれぞれ、CSVファイルの価値と重さの情報ですので、それらを使用してItemクラスのインスタンスを作成します(21行目)。
そして22行目で作成したインスタンスを、Itemクラスのクラス変数であるitems_list(リスト)に追加していきます。

これで、CSVファイルを読み込んでアイテムの情報をプログラムで使える状態になりました。

パラメータクラスの作成

Parameter.pyは、ナップサック問題やGAで使用するパラメータをまとめたクラスです。

Parameter.py

# -*- coding: utf-8 -*-

import datetime
from Item import Item

class Parameter:

    # 入力ファイル名
    INPUT_FILE_NAME = "./items.csv"

    POP_SIZE = 100          # 母集団サイズ(個体数)
    MAX_GENERATION = 50;    # 世代数
    SEED = 0                # 乱数のシード

    GENE_LENGTH = -1        # 遺伝子長(=アイテム数)
    CAPACITY = 9999999      # ナップザックの容量(重さの総和の半分とし、あとで計算する)
    MUTATION_TATE = 0       # 突然変異率(アイテム数から計算する)

    OUTPUT_INTERVAL = 10    # 結果をファイル出力する世代数の間隔


    @staticmethod
    # 遺伝子長を設定する
    def set_genes_length(length):
        Parameter.GENE_LENGTH = length

    @staticmethod
    # ナップザックの容量を計算(全アイテムの重さの総和の半分とする)
    def set_capacity():
        weight_sum = 0
        for i in range(0, len(Item.items_list)):
            weight_sum += Item.items_list[i].weight

        Parameter.CAPACITY = weight_sum / 2

    @staticmethod
    # アイテム数から、突然変異率を計算する
    def set_mutation_rate():
        Parameter.MUTATION_TATE = 1 / float(Parameter.GENE_LENGTH)

まずは変数の説明です。コメントを見ればわかるであろうものについては、説明を省略します。

9行目のINPUT_FILE_NAMEは、ナップサック問題のアイテム情報が記載されたCSVファイル名です。

12行目のMAX_GENERATIONは、GAで使用するパラメータである最大世代数です。GAの親選択、交叉、突然変異、評価の一連の流れを世代といいます。この世代数の数だけ、GAを繰り返します。

13行目のSEEDは、プログラムの乱数で使用するシードを表します。プログラムの乱数は、正確にはある一定のパターンで値を出力します。さらに、同じシードの値を使用した乱数は、プログラムを繰り返すたびに同じ順番で同じ乱数を得ることができます。つまり、乱数のシードを固定した場合、乱数の順番は毎回同じとなり、プログラムで乱数を使用していたとしても毎回同じ結果を得ることができます。研究でプログラムを使用する場合に結果を再現したり、バグを再現する際に、シードを固定していないと同じ結果を再現することができませんので、毎回結果が異なるゲームや占いプログラムでない限り、少なくとも開発中はシードを固定するようにしておきましょう。

15行目のGENE_LENGTHは、遺伝子の長さです。GAでナップサック問題を解く場合、遺伝子長は総アイテム数と等しくなります。あとでアイテム数を数えて値をセットするため、とりあえず未設定を表す-1で初期化しています。
16行目のCAPACITY(ナップサックの容量)も後で計算するため、とりあえず無限大(9,999,999)で初期化しています。ちなみに、今回のナップサック問題では、ナップサックの容量を下記のように定義しています。

$$ナップサックの容量=\frac{アイテムの重さ総和}{2}$$

17行目のMUTATION_TATEは、GAのパラメータである突然変異率を表します。遺伝子の各値は、それぞれこの突然変異率で突然変異が起こります。一般的に突然変異率は下記のように定義されています。

$$突然変異率(\%)=\frac{1}{遺伝子長}$$

突然変異率が高いほど、子の遺伝子が親の値を受け継ぎにくくなります。逆に、突然変異率が低いほど、子の遺伝子が親の値を受け継ぎやすくなります。

19行目のOUTPUT_INTERVALはプログラムで使用するパラメータで、結果をCSVに出力する間隔を示します。例えば10に設定すれば、10世代ごとに母集団内の遺伝子の情報をCSVに出力します。結果を出力する処理は別の箇所に記載していますので、別途説明します。

次にメソッドの説明です。
24〜25行目は、引数の値を、遺伝子長に設定するメソッドです。

29〜34行目は、ナップサックの容量(全アイテムの重さの総和の半分とする)を計算するメソッドです。31〜32行目でアイテムの重さの合計を計算し、34行目で総和を2で割った値を戻り値として返しています。

38〜39行目は、アイテム数から突然変異率を計算するメソッドです。突然変異率の計算方法については、上で説明したとおりです。

結果出力クラスの作成

OutputCsv.pyは、プログラムの結果をCSVに出力するクラスです。

OutputCsv.py

# -*- coding: utf-8 -*-

# CSVファイル書き込みクラス
class OutputCsv:
    def __init__(self, filename):
        self.file_name = filename    # 出力ファイル名


    # ファイル追記
    def write(self, string):
        f = open(self.file_name, 'a')
        f.write(str(string))

        f.close()

    # ファイル追記
    def write_line(self, string):
        f = open(self.file_name, 'a')
        f.write(str(string) + "\n")

        f.close()

5〜6行目のコンストラクタは、結果を出力するファイル名を引数に受け取り、変数file_nameに格納します。

9〜14行目は、変数file_nameにセットされたファイル名のファイルに、引数で受け取った文字列を追記するメソッドです。
17〜21行目は上記のメソッドに似ていて、異なるのは19行目だけです。writeメソッドは追記に改行を含みませんが、write_lineは改行を含みます。場合によって使い分けます。

ユーティリティクラスの作成

Util.pyは、プログラムで使用するユーティリティメソッドをまとめたクラスです。ユーティリティクラスには再利用性の高いメソッドをまとめています(他のプログラムを作るたびに進化していく...!)。

Util.py

# -*- coding: utf-8 -*-

import random
from datetime import datetime
from OutputCsv import OutputCsv
from Parameter import Parameter
import os.path


# ユーティリティクラス
class Util:

    random.seed(Parameter.SEED)      # シードは固定しておく

    @staticmethod
    # 0〜100の乱数を取得する
    def get_rand(max_num):
        return random.randint(0, max_num)

    folder_name = None  # 結果出力用のフォルダ名

    @staticmethod
    # 結果出力用のフォルダ名を設定
    def set_folder_name():
        if Util.start_time is None:
            init_start_time()
        Util.folder_name = Util.start_time


    @staticmethod
    # 現在の世代の全ての解の情報をcsvファイルに出力
    def write_result(p, generation): 
        # フォルダが未作成の場合は作成
        if not os.path.isdir(str(Util.folder_name)):
            os.mkdir(str(Util.folder_name))

        # ディレクトリを移動する
        os.chdir(str(Util.folder_name))

        # フォルダ内にファイル出力
        filename = str(Util.folder_name) + "_result" + str(generation) + ".csv"
        writer = OutputCsv(str(filename))

        p.output_result(writer)        # csvファイルにその世代の全ての解を書き出す

        # ディレクトリを戻る
        os.chdir(str(".."))

    @staticmethod
    # csvファイルにその世代の最良解の情報を書き出す
    def write_best(p):
        # フォルダが未作成の場合は作成
        if not os.path.isdir(str(Util.folder_name)):
            os.mkdir(str(Util.folder_name))

        # ディレクトリを移動する
        os.chdir(str(Util.folder_name))

        # フォルダ内にファイル出力
        filename = str(Util.folder_name) + "_best" + ".csv"
        writer = OutputCsv(str(filename))

        p.output_best(writer)           # csvファイルにその世代の最良解の情報を書き出す

        # ディレクトリを戻る
        os.chdir(str(".."))


    #+++++++++++++++++++++++++++++++++++++++++
    #  時間関係
    #+++++++++++++++++++++++++++++++++++++++++

    start_time = None   #プログラム開始時刻

    @staticmethod
    # 計算開始時刻を設定
    def init_start_time():
        Util.start_time = datetime.now().strftime("%Y%m%d_%H%M%S")

13行目では、前回の記事で説明したとおり、乱数のシードを固定しています。
17〜18行目は、受け取った値を最大値とした乱数を返すメソッドです。

20行目は、結果出力ファイルをまとめるフォルダ名を示す変数です。結果ファイルはこのフォルダに出力するようにします。値は後で設定するため、Noneにしています。話はそれますが、他の言語でいうところのNullを示すには、PythonではNoneなんですね。今回知りました。

24〜27行目は、結果出力用のフォルダ名を設定するメソッドです。25〜26行目で変数start_timeが空だった場合、init_start_time()を実行するようにしています(これは後述します)。そして、変数folder_nameに、変数start_timeの値を代入しています。

先に73行目以降の説明をします。
77〜78行目は、変数start_timeに現在時刻を格納するメソッドです。フォーマットは、"%Y%m%d_%H%M%S"としておりますので、現在日時が2018/7/2 10:20:05であれば、"20180702_102005"となります。27行目で変数start_timeの値を変数folder_nameにセットしていましたね。つまり出力用のフォルダ名は、現在時刻の文字列になります。

32〜47行目は、プログラムの結果をCSVファイルに出力するメソッドの1つです。このメソッドは、現在の世代の全ての解の情報をCSVファイルに出力します。引数のpは後述するPopulationクラスのインスタンス、generationは現在の世代数です。
34〜35行目では、変数folder_nameの名前のフォルダが存在しない場合、変数folder_nameの名前のフォルダを作成します。

38行目では、先ほど作成したフォルダ内にファイルを作成するために、カレントディレクトリ(現在作業しているフォルダのことです)を移動します。

41行目では、出力ファイル名(filename)を設定しています。出力ファイル名は、"フォルダ名"_result"generation".csvのような名前になります。こうすることで、ファイル名を見るだけでいつ実行したプログラムの結果なのかがすぐわかるようにしています。

ところで、所々変数をstr()で囲っています。これは、変数を文字列に変換するメソッドですが、このようにos系のメソッドを使用する際に明示的に文字列型だと指定しないと、エラーが発生します。

42行目で、OutputCsvクラスのインスタンス変数(writer)を作成しています。
44行目で、Populationクラスのメソッド(CSVファイルにその世代の全ての解を書き出す)を呼び出しています。このメソッドについては、Populationクラスのところで説明します。

最後に47行目で、変更したカレントディレクトリを元に戻しています。

51〜66行目は、上述した32〜47行目のメソッドに似ており、CSVファイルにその世代の最良解の情報を書き出すメソッドです。
異なるのは、60行目のファイル名と、63行目で呼び出しているメソッドです。63行目のメソッドはPopulationクラスのメソッドですので、後述します。

遺伝子個体クラスの作成

いよいよGAの部分の説明に入っていきます。
Individual.pyは、1つの個体(ナップサック問題でいえば、1つの解)を示すクラスです。

Individual.py

# -*- coding: utf-8 -*-

import random
from Item import Item
from Parameter import Parameter
from Util import Util
from OutputCsv import OutputCsv

# 個体クラス
class Individual:

    def __init__(self, length):
        self.genes = []         # 遺伝子
        self.select_p = 0       # 個体の選択確率
        self.weight = 0         # 重さ
        self.fitness = 0        # 評価値

        # 遺伝子の初期化
        for i in range(0, length):      
            # 0〜100の乱数を取得
            num = Util.get_rand(100)

            if num % 2 == 0:
                self.genes.append(False)   # 0を表現
            else:
                self.genes.append(True)    # 1を表現


    # 個体を評価する
    def evaluate(self):
        fitness_sum = 0
        weight_sum = 0

        for i in range(0, len(self.genes)):

            # アイテムが選択されている場合、価値と重さを加算
            if self.genes[i]:
                item = Item.items_list[i]
                fitness_sum += item.value
                weight_sum += item.weight

        # 容量オーバーの個体は、評価値を1に設定する
        if weight_sum > Parameter.CAPACITY:
            fitness_sum = 1

        self.fitness = fitness_sum
        self.weight = weight_sum


    # 一点交叉
    def one_point_crossover(self, parent1, parent2):
        location = Util.get_rand(len(self.genes))       # 交叉の際に区切る位置を決める
        mask = []                                       # 交叉時に使用するマスク作成

        # マスクを設定 falseなら入れ替える、trueなら入れ替えない
        for i in range(0, len(self.genes)):
            if location >= 0:
                mask.append(True)
            else:
                mask.append(False)
            location -= 1

        # マスクを使用して遺伝子を入れ替える
        for i in range(0, len(mask)):
            if mask[i]:
                # マスクがtrueなら 親1の遺伝子が入る
                self.genes[i] = parent1.genes[i]
            else:
                # マスクがfalseなら親2の遺伝子が入る
                self.genes[i] = parent2.genes[i]

        self.fitness = 0    # 評価値を初期化する


    # 突然変異
    def mutation(self):
        for i in range(0, len(self.genes)):
            if Parameter.MUTATION_TATE * 100 > Util.get_rand(100):
                self.genes[i] = not self.genes[i]


    # csvファイルに解の情報を書き出す
    def output_result(self, writer):
        # 評価値
        writer.write(self.fitness)
        writer.write(",")

        # 重さ
        writer.write(self.weight)

        # 遺伝子
        for i in range(0, len(self.genes)):
            writer.write(",")

            # bool値を数値に変換
            if self.genes[i]:
                writer.write(1)
            else:
                writer.write(0)

        writer.write_line("")

12〜26行目がIndividualクラスのコンストラクタで、引数で遺伝子の長さ(length)を受け取ります。

13〜16行目で、Individualクラスのメンバ変数を定義しています。
13行目の遺伝子は、boolean型の配列です。つまり、trueかfalseで遺伝子の0か1を表現します(1がtrueに対応しています)。
14行目の選択確率とは、後述する親選択方法の1つであるルーレット選択で使用します。この確率が高い個体ほど、親に選択されやすくなります。
16行目の評価値とは、遺伝子を評価した時の値です。つまり、評価値が高い個体ほど、良い個体ということです。具体的に今回解くナップサック問題では、重さの総重量がナップサックの容量以内であり、価値の高いアイテムを含んでいるほど評価値が高くなります。

19〜26行目で、遺伝子配列を初期化します。
21行目で0〜100の間の乱数を取得します。乱数が偶数であればFalse、奇数であればTrueを遺伝子配列に入れていきます。

評価

評価とは、GAのメカニズムの1つで、個体がどれだけ優れているかを値で表します。
問題に応じてここの評価方法は異なります。今回はナップサック問題であるので、繰り返しになりますが重さの総重量がナップサックの容量以内であり、価値の高いアイテムを含んでいるほど評価値が高くなります。

具体的にコードを見ていきます。
30〜47行目が、評価メソッドです。遺伝子が示すアイテムの総重量と総価値を計算するため、31、32行目で変数を初期化します。
37〜40行目で遺伝子の値を順番に見ていき、Trueであればその遺伝子のインデックスのアイテムをitems_listから取り出し(38行目)、重さと価値をそれぞれ加算します(39〜40行目)。

そして重さの総和がナップサックの容量を超えていた場合は、制約違反として実行不可能解になります。実行不可能解はルール(制約)を守っていませんので、その個体の評価値を1にします(44行目)。
GAによって実行不可能解の扱いは異なります。例えば、評価値を半分にするなどです。

46、47行目で個体の価値総和と重さの総和を変数に格納して終了です。

交叉

交叉とは、GAのメカニズムの1つで、ある親選択手法により選択された2つの親個体から、子個体を生成するメカニズムです。交叉により、親の特徴を引き継いだ子個体が生成されます。

交叉にはいろんな種類がありますが、今回はシンプルである一点交叉を使用します。
51〜72行目が一点交叉のメソッドです。引数で2つの親個体を受け取ります。
52行目で、交叉の際に区切る位置(交叉点)を乱数で決めます。
53行目のmaskは、遺伝子と長さが同じboolean型の配列で、交叉の時に使用します。2つの親をそれぞれ親1、親2とすると、maskの値がtrueであれば、その位置には親1の値が入ります。maskの値がfalseであれば、その位置には親2の値が入ります。そうしてできた遺伝子が新たな子個体となります。

先に交叉メソッドの流れを説明してしまいましたが、56〜61行目でmaskの値を、52行目で決定した交差点を基に設定しています。

64〜70行目では、上述のとおり、maskの値に応じて遺伝子に親1と親2の値を格納していきます。

最後に、遺伝子の情報が変わりました(新たに子個体となりました)ので、評価値を0にリセットしておきます。

突然変異

突然変異とは、突然変異率に基づいて、遺伝子の値を変更するメカニズムです。突然変異率については、Parameterクラスのところで説明しましたね。

突然変異方法にも色々な方法がありますが、今回は0と1をビット反転させるシンプルな突然変異を使用します。
66〜69行目が突然変異のメソッドです。

乱数の値が突然変異率以下であれば(78行目)、遺伝子のTrueとFalseを入れ替えます(79行目)。

遺伝子情報の出力

83〜101行目は、遺伝子の情報をCSVファイルに出力するメソッドです。引数でOutputCsvクラスのインスタンス変数を受け取ります。
出力する情報は、評価値(85行目)、重さ(89行目)、遺伝子配列(92〜99行目)です。遺伝子配列(genes)にはtrueかfalseの論理値が入っていますので、96〜99行目で0と1に変換しています。

母集団クラスの作成

Population.pyは、個体全体をまとめた母集団を示すクラスです。

Population.py

# -*- coding: utf-8 -*-

from Individual import Individual
from Util import Util
from OutputCsv import OutputCsv

# 母集団クラス
class Population:

    def __init__(self, num, length):
        self.population = []        # 母集団

        # 遺伝子の個体を母集団サイズの数だけ生成する
        for i in range(0, num):
            self.population.append(Individual(length))


    # x番目とy番目の遺伝子個体を入れ替える
    def swap(self, x, y):
        temp = self.population[x]
        self.population[x] = self.population[y]
        self.population[y] = temp


    # 遺伝子を評価値で降順バブルソートする
    def bubble_sorf(self):
        for i in range(0, len(self.population) - 1):
            for j in range(0, len(self.population) - i - 1):
                if self.population[j].fitness < self.population[j + 1].fitness:
                    self.swap(j, j + 1)


    # ルーレット選択の選択確率を決定する(母集団の上半分から計算する)
    def calc_select_p(self):
        sum_fitness = 0;        #評価値の合計
        for i in range(0, len(self.population) / 2):
            sum_fitness += self.population[i].fitness

        for i in range(0, len(self.population) / 2):
            # 個体Aの評価値 / 母集団上半分の個体の評価値合計 = 個体Aの選択確率
            self.population[i].select_p = self.population[i].fitness * 100 / float(sum_fitness)

    # ルーレット選択で母集団の上半分から個体を1つ選択する
    def roulette_selection(self, percent):

        sum_p = 0   # 選択確率を蓄積していく変数
        p_size = len(self.population)

        selected_index = p_size - 1     #選択された個体の番号

        for i in range(0, p_size / 2):
            sum_p += self.population[i].select_p
            if sum_p > percent:
                selected_index = i
                break

        return self.population[selected_index]      # 選択された個体を返す


    # 子個体を母集団の下半分の数だけ生成する
    def crossover(self):
        p_size = len(self.population)   # 母集団サイズ

        for i in range(p_size / 2, p_size):
            # 母集団から親を選ぶ 同じ親を選んだらやりなおし
            while True:
                # ルーレット選択で親個体を2つ選択する
                parent1 = self.roulette_selection(Util.get_rand(100))
                parent2 = self.roulette_selection(Util.get_rand(100))

                if parent1 != parent2:
                    break

            self.population[i].one_point_crossover(parent1, parent2)     #交叉


    # 母集団の個体を評価する
    def evaluate(self):
        for i in range(0, len(self.population)):

            # 評価値が未設定の個体のみ評価する
            if self.population[i].fitness <= 0:
                self.population[i].evaluate()


    # 母集団内の新たに生成された個体を突然変異する
    def mutation(self):
        for i in range(0, len(self.population)):

            # 評価値が未設定の個体のみ評価する
            if self.population[i].fitness <= 0:
                self.population[i].mutation()


    # csvファイルにその世代の全ての解の情報を書き出す
    def output_result(self, writer):
        writer.write_line("Fitness,Weight,Gene")

        # 各遺伝子の情報を出力
        for i in range(0, len(self.population)):
            self.population[i].output_result(writer)


    # csvファイルにその世代の最良解の情報を書き出す
    def output_best(self, writer):
        self.population[0].output_result(writer)</pre>

10〜15行目はコンストラクタです。引数で母集団サイズ(num)と、遺伝子長(length)を受け取ります。
11行目の変数populationは、Individualクラスのインスタンスのリストです。
14〜15行目で、Individualクラスのインスタンスを作成し、リスト(変数population)に追加していきます。

バブルソートの実装

母集団内の個体を、評価値の降順でソートするために、バブルソートを実装します。ソートの手法には色々なものがありますが、今回は実装が簡易であるバブルソートを実装しました。

19〜22行目は、引数でxとyの2つの値を受け取り、母集団内x番目とy番目の遺伝子個体の順番を入れ替えるメソッドです。このメソッドは、後述するbubble_sorfメソッドで使用します。

26〜30行目は、母集団内の個体を、評価値の高い順に並び替える(ソート)するメソッドです。
29行目で順番が隣の遺伝子同士の評価値を比較し、降順になっていなかったら上記で説明したのswapメソッドを使用して個体の順番を入れ替えます(30行目)。

ルーレット選択

34〜41行目は、ルーレット選択(親選択方法の1つ)で使用する各個体の選択確率を決定するメソッドです。後述する交叉の処理で親個体を選択する際に使用します。
ルーレット選択は、評価値に基づいて選択確率を計算し、選択確率を使用して親個体を選択します。個体の評価値が高いほど選択確率が高くなり、選択されやすくなります。今回、親個体は母集団の上半分から選択するようにします。その場合例えば、個体Aの選択確率は下記のように計算できます。

$$個体Aの選択確率(\%) = \frac{Aの評価値}{母集団上半分の個体の評価値合計}$$

具体的には、35〜37行目で母集団上半分の個体の評価値合計を計算します。
39〜41行目で、各個体の選択確率を計算します。
44〜57行目は、ルーレット選択で母集団の上半分から個体を1つ選択するメソッドです。引数は、0〜100の乱数です。
49行目の変数selected_indexは、選択された親個体の番号を格納する変数で、母集団内の一番最後の個体番号で初期化しています。
51〜55行目で、母集団内の選択確率が高い個体順に、選択確率を足していきます(52行目)。選択確率の累計値(sum_p)が、変数percentの値より大きくなった場合、変数selected_indexにその番号を格納します。
最後に57行目で、選択された番号の個体を戻り値として返します。

交叉

61〜74行目は、子個体を母集団の下半分の数だけ新たに生成(交叉)して入れ替えるメソッドです。
68、69行目で、上述したルーレット選択メソッドを使用して親個体をそれぞれ選択し、parent1とparent2に格納しています。異なる親個体が選択された場合のみ、whileの無限ループを抜け出します(71〜72行目)。もし同じ親個体が選択された場合は、処理をやり直します。

74行目で、Individualクラスに作成した交叉メソッド(one_point_crossover)を呼び出し、選択した2つの親個体を交叉し、個体を新たに生成します。

個体の評価

78〜83行目は、母集団全体の個体を評価するメソッドです。
評価については、Individualクラスのところで説明いたしました。
具体的にソースコードでは、母集団内の各個体について、評価値が0(未設定)である個体に対してIndividualクラスのevaluateメソッドを呼び出しています(82〜83行目)。

評価値が未設定の個体のみ評価しているのは、簡易実装にしているためです。より正確に実装するのであれば、新たに生成された母集団下半分の個体のみ評価すればOKです。ですが、こちらの方がコードを書くのが楽だったため、このような実装をしています(遺伝子は交叉によって生成された時に評価値を0で初期化していましたよね)。

突然変異

87〜92行目は、母集団内の新たに生成された個体を突然変異させるメソッドです。
突然変異も上記の評価と同様に、評価値が0(未設定)である個体に対してIndividualクラスのmutationメソッドを呼び出しています(87〜92行目)。

結果の出力

96〜101行目は、CSVファイルにその世代の全ての解の情報を書き出すメソッドです。
97行目で各列の項目名(Fitness、Weight、Gene)を出力し、101行目で各個体(Individualクラス)のoutput_resultメソッドを呼び出して遺伝子情報を書き出しています。

105〜106行目は、CSVファイルにその世代の最良解の情報を書き出すメソッドです。
106行目のとおり、最良解はソートにより母集団の一番先頭にありますので、population[0]のoutput_resultメソッドを呼び出して遺伝子情報を書き出しています。

メインクラスの作成

Main.pyは、その名のとおりメイン処理が書かれたクラスです。プログラムを実行するには、"python Main.py"とコマンドを入力します。

Main.py

# -*- coding: utf-8 -*-

from InputCsv import InputCsv
from Parameter import Parameter

from Util import Util
from Item import Item
from Individual import Individual
from Population import Population
import sys

# -- Main --

# ファイルを読み込みデータを取得する
reader_csv = InputCsv(Parameter.INPUT_FILE_NAME)
if not reader_csv.read():
    print("ファイル読み込みに失敗したため、処理を終了します")
    sys.exit()    # 処理異常終了

# アイテムの情報を初期化する
Item.init_items(reader_csv.input_str)

# 遺伝子長を設定する
Parameter.set_genes_length(len(Item.items_list))

# ナップザックの容量を設定する
Parameter.set_capacity()

# 突然変異率を設定する
Parameter.set_mutation_rate()

# 母集団を作成する
population = Population(Parameter.POP_SIZE, Parameter.GENE_LENGTH)

# 計算開始時刻を設定
Util.init_start_time()
# 結果出力用のフォルダ名を設定
Util.set_folder_name()

# ループ開始
for g in range(0, Parameter.MAX_GENERATION + 1):

    # 母集団内の個体を評価する
    population.evaluate()

    # 評価値でソートする
    population.bubble_sorf()

    # csvファイルにその世代の最良解の情報を書き出す
    Util.write_best(population)

    # Parameterクラスで定めた世代数毎に結果をファイル出力
    if (g % Parameter.OUTPUT_INTERVAL) == 0 and g != 0:
        Util.write_result(population, g)

    # 選択確率を計算する
    population.calc_select_p()

    # 交叉する
    population.crossover()

    # 突然変異する
    population.mutation()

    print("世代数: " + str(g))

Mainクラスはほぼほぼコメントに記載したとおりの流れでメソッドを次々と読んでいるだけなので、コメントを追っていただければ説明は必要ないかと思います。

わからなさそうなところだけ説明します。

16〜18行目では、読み込むCSVファイル(ナップサック問題のアイテムが記載されたファイル)が存在しない場合、プログラムを終了させる処理です。

41〜65行目がGAのループです。1ループのことをGAでは"1世代"といいます。

65行目では、printメソッドで現在の世代数をコンソールに出力しています。不要であれば消して問題ありません。

結果と考察

3施行、プログラムを実行しました(乱数シードを変更して実行したということです)。3回しか実行していませんが、大学の研究などであれば5〜10回は施行して結果を詳細に見た方が良いかと思います。

下記の図は、各世代の最優良解をプロットしたもので、縦軸が最良解遺伝子の評価値、横軸が世代数を示しています。それぞれの試行で色を分けています。

どの施行も、30世代ちょいで収束(それ以上進化しないこと)していることがわかりますね。収束時の遺伝子の評価値は"908"でした。以前、全く同じ例題で全探索を実施したのですが、たしかその時の最適解が"908"であったと記憶しておりますので、最適化を見つけることができています(これぐらいの簡単なナップサック問題であれば、全探索でもすぐ終わります)。

GAの計算時間は、これぐらいの問題であれば一瞬です。

最後に

結果のプロット図を見ると、少しずつ解が進化していき、評価値が上がっていくのが見れると思います。
アイテム数や世代数を変更して実行してみるのもおもしろいですよ。
少しでもGAに興味を持っていただけたら嬉しいです！

プログラムのソースコードを読んで、もしアドバイスなどありましたらコメントください！(私はPythonの経験が無いので)
今後は多目的最適化(2目的ナップサック問題)の解説記事も書こうかなーと考えています。