RのGAライブラリ[コード編] RのGAは超シンプルです。

最適化 / メタヒューリスティック

GAの基本的な使い方(R編)

GAのモードは3種類あります。
“real-valued”, “binary”, “permutation”の3つです。
つまり、実数値、バイナリ、順列の3つです。
交差方法が異なるので、適切なものを選ばないといけません。
一つ一つ適用例をみていきます。

実数型

曲線の最小値を求める問題

テストケースとして、|x| + cos(x)の最小値を求める問題を解いてみます。
GAのパッケージとして、評価関数が大きな値が評価されるので、評価関数は正負反転したこの関数そのものであり、解の表現として、染色体は1つです。
この場合、評価関数と最適化したいものが同じです。

引数の説明

typeはタイプ。
fitnessは評価関数。
lower,upperは、探索範囲の下限値と上限値
popSizeは個体数。
maxiterは進化する繰り返し数。
optimは、局所探索をするかどうか。
局所探索とは、近傍を探すというアルゴリズムを入れるかどうかである。
今回のものは近傍探索しないとたどり着けそうにないので、入れた。
局所探索のアルゴリズムは以下。
1.解を一つランダムに生成する。
2.現在の解の近傍の内一つをある条件で選び近傍解とする。
3.定義した条件を満たすなら、近傍解を現在の解と入れ換える。
4.終了条件を満たすまで 2. 以下を繰り返す。
詳しくは資料でもみてください。

x1
0

最小値を発見している模様。

染色体が1つだと寂しいので2つのやつをやる。

多峰性関数

多峰性関数は最小値ではない極値にハマりやすいので、最適化アルゴリズムのテストによく使われる。


こういう関数は、局所探索をするとすごくうまくいく
optim=FALSEだと意外とうまく行かない

バイナリ型

0か1を取るバイナリ型のGAで問題を解いてみる

ナップサック問題

ナップサック問題とは、状況として、値段のついた物が色々あって、リュックに詰められる重さ(体積)が決まってます。その場合リュックの制限容量に対して最適な組み合わせで、値段が最大になるようにものを選んでいくと言う問題。


特徴量抽出みたいなこと。

<適当な直訳>
統計的モデリングにおけるバイナリGAの典型的な用途はサブセット選択である。一組のp個の予測子が与えられると、サブセット選択は、応答変数の変動を説明するのに最も関連性のある予測子を識別することを目的とする。これは未知のパラメータの節約を達成することを可能にし、より良い推定とより明確な回帰係数の解釈の両方をもたらします。サブセット選択の問題は、1が予測子の存在を示し、0が所定の候補サブセットからの不在を示す、2進ストリングを使用してGAによって自然に処理することができます。候補サブセットの適合度は、AIC、BICなど、いくつかのモデル選択基準のうちの1つによって測定できます。

UsingRがないとこれは動かないので、Rから
install.packages(‘UsingR’)でインストールしてください。

順列型

巡回セールスマン問題

Athens Barcelona Brussels Calais Cherbourg Cologne Copenhagen Geneva Gibraltar Hamburg Lisbon Lyons Madrid Marseilles Milan Munich Paris Rome Stockholm Vienna
Athens 0 3313 2963 3175 3339 2762 3276 2610 4485 2977 4532 2753 3949 2865 2282 2179 3000 817 3927 1991
Barcelona 3313 0 1318 1326 1294 1498 2218 803 1172 2018 1305 645 636 521 1014 1365 1033 1460 2868 1802
Brussels 2963 1318 0 204 583 206 966 677 2256 597 2084 690 1558 1011 925 747 285 1511 1616 1175
Calais 3175 1326 204 0 460 409 1136 747 2224 714 2052 739 1550 1059 1077 977 280 1662 1786 1381
Cherbourg 3339 1294 583 460 0 785 1545 853 2047 1115 1827 789 1347 1101 1209 1160 340 1794 2196 1588
Cologne 2762 1498 206 409 785 0 760 1662 2436 460 2290 714 1764 1035 911 583 465 1497 1403 937
Copenhagen 3276 2218 966 1136 1545 760 0 1418 3196 460 2971 1458 2498 1778 1537 1104 1176 2050 650 1455
Geneva 2610 803 677 747 853 1662 1418 0 1975 1118 1936 158 1439 425 328 591 513 995 2068 1019
Gibraltar 4485 1172 2256 2224 2047 2436 3196 1975 0 2897 676 1817 698 1693 2185 2565 1971 2631 3886 2974
Hamburg 2977 2018 597 714 1115 460 460 1118 2897 0 2671 1159 2198 1479 1238 805 877 1751 949 1155
Hook of Holland 3030 1490 172 330 731 269 269 895 2428 550 2280 863 1730 1183 1098 851 457 1683 1500 1205
Lisbon 4532 1305 2084 2052 1827 2290 2971 1936 676 2671 0 1178 668 1762 2250 2507 1799 2700 3231 2937
Lyons 2753 645 690 739 789 714 1458 158 1817 1159 1178 0 1281 320 328 724 471 1048 2108 1157
Madrid 3949 636 1558 1550 1347 1764 2498 1439 698 2198 668 1281 0 1157 1724 2010 1273 2097 3188 2409
Marseilles 2865 521 1011 1059 1101 1035 1778 425 1693 1479 1762 320 1157 0 618 1109 792 1011 2428 1363
Milan 2282 1014 925 1077 1209 911 1537 328 2185 1238 2250 328 1724 618 0 331 856 586 2187 898
Munich 2179 1365 747 977 1160 583 1104 591 2565 805 2507 724 2010 1109 331 0 821 946 1754 428
Paris 3000 1033 285 280 340 465 1176 513 1971 877 1799 471 1273 792 856 821 0 1476 1827 1249
Rome 817 1460 1511 1662 1794 1497 2050 995 2631 1751 2700 1048 2097 1011 586 946 1476 0 2707 1209
Stockholm 3927 2868 1616 1786 2196 1403 650 2068 3886 949 3231 2108 3188 2428 2187 1754 1827 2707 0 2105
Vienna 1991 1802 1175 1381 1588 937 1455 1019 2974 1155 2937 1157 2409 1363 898 428 1249 1209 2105 0

整数型

GAのこのパッケージには基本的に整数型はありません。
使いたいなら、もうちょい拡張性の高いパッケージを使えばいいだけの話なのですが、これにはないです。そして、あんまし色々パッケージを使うのは、インフラ上めんどいので、練習も兼ねてこのパッケージで実装する方法を考えてみます。

ここでは、例としてナップサック問題で、複数個取れる状況を考えてみます。

バイナリ版

まず、バイナリ型で解くことを考えてみます。
この場合、単純に考えれば、全く同じ値段、重さのものをもう一個加えるとすればいいでしょう。しかし、これは効率が悪いです。なぜなら、こう考えると、一個目を取るor取らないで0か1,もう一個もとる取らないで0か1で、結局0~2までの値を取ることしかできません。しかし、バイナリで2つの染色体を使うのであれば、2進法で0~3までの値を表現できます。 染色体が3つになれば、前者は0~3までしか取れませんが、2進法で表現すれば、0~7までの値を表現することができます。

これで見えてきました。
バイナリ型の染色体を複数使って2進法でそれを一つの数字とみなしてやれば、整数型を実装できそうです

しかし、2進法で表現するのはあまりよくない点があります。いわゆるハミング距離で考えると微妙です。ハミング距離とは、長さの等しい2つの文字列において、対応するいちにあって値が異なる文字の個数です。

つまりは、0111と、1000は7と8で近い数なのに、表現としては大きく文字列が変わってしまいます。差と2進数でのハミング距離の組み合わせが様々になっていて、GAでの探索時に不都合が出ることが多いです。
そこでグレイコードを使用します。
グレイコードでは 上下に隣り合うものはいずれも値が異なるビットは1つのみであることがわかります。

2進数とグレイコードの変換
参考 : https://en.wikipedia.org/wiki/Gray_code

10進数と2進数の変換

ナップサック問題で、どれも1~3個目は3つまで、4,5個目は5個、6,7個目は1つ取れるとします。解いてみましょう。

実数版

実数型のGAの方法を考えてみると、交差では2つの値の間(外もだけど)の解を探しているだけなので、実数値で出てきたものを四捨五入とか切り捨てとかでやっても大丈夫なんじゃないか?という発想が湧いてきます。実際、GAの場合はまずまず大丈夫です。普通の最適化計算ではこのようなやり方は禁じ手なのですが、GAの場合はまあまあいけます。素晴らしいですね。交差等の仕方にもよりますが、四捨五入がいいのではと思います。やってみましょう。

やるとわかりますが、やはり四捨五入は微妙です。(そりゃそうだ)
何度かやってもバイナリでやったやつの方がいい答えにたどり着く確率が高いのがわかると思います。
しかし、実数型のなかに四捨五入しなきゃいけないものがあっても割と使えるよ、というのは驚くべきことです。

 



[
前の記事へ]  [最適化/進化計算の目次へ]  [次の記事へ]