<?php
/***********************************/
/* 遺伝的アルゴリズムによるTSPの解 */
/* coded by Y.Suganuma */
/***********************************/
/***********************/
/* クラスSpeciesの定義 */
/***********************/
class Species {
protected $max; // 最大適応度
protected $mean; // 平均適応度
protected $pi; // 適応度
protected $ro; // ルーレット板
protected $allele_u; // 対立遺伝子上限
protected $allele_l; // 対立遺伝子下限
protected $size; // 個体総数
protected $max_ch; // 子供の数の最大値
protected $max_len; // 最大遺伝子長
protected $min_len; // 最小遺伝子長（負の時は，最大遺伝子長で固定）
protected $max_n; // 最大適応度の個体番号
protected $dup_a; // 遺伝子の重複
// =0 : 重複を許さない
// =1 : 重複を許す
protected $dup_s; // 個体の重複（同じ染色体の個体）
// =0 : 重複を許さない
// =1 : 重複を許す
protected $ind; // 集団（個体の集まり）
protected $len; // 各個体の遺伝子長
protected $kou1; // 交叉・突然変異用作業場所１
protected $kou2; // 交叉・突然変異用作業場所２
protected $s_w; // 淘汰用指標（選択された回数）
protected $edge; // エッジ組み替え交叉用ワークエリア
protected $pi_w; // 適応度計算指標
// =0 : 未使用
// =1 : 適応度計算前（突然変異はこの個体だけに適用）
// =2 : 適応度計算済み（交叉時に親とみなす）
/****************************/
/* コンストラクタ */
/* name : ファイル名 */
/* seed : 乱数の初期値 */
/****************************/
function Species($name, $seed)
{
/*
データの入力
*/
$in = fopen($name, "rb");
fscanf($in, "%*s %d %*s %d", $this->allele_u, $this->allele_l);
fscanf($in, "%*s %d %*s %d", $this->max_len, $this->min_len);
fscanf($in, "%*s %d %*s %d", $this->dup_a, $this->dup_s);
fscanf($in, "%*s %d %*s %d", $this->size, $this->max_ch);
/*
データのチェック
*/
if ($this->size <= 0)
exit("***error 個体総数≦０ (Constructor)\n");
if ($this->max_ch < 0)
exit("***error 子供の数＜０ (Constructor)\n");
if ($this->max_len <= 0 || $this->min_len == 0)
exit("***error 遺伝子長≦０ (Constructor)\n");
if ($this->max_len < $this->min_len)
exit("***error 最大遺伝子長＜最小遺伝子長 (Constructor)\n");
if ($this->allele_u <= $this->allele_l)
exit("***error 対立遺伝子上限≦対立遺伝子下限 (Constructor)\n");
$kind = $this->allele_u - $this->allele_l + 1;
if ($this->dup_a == 0 && $this->max_len > $kind)
exit("***error 遺伝子の重複を防ぐことはできない (Constructor)\n");
/*
領域の確保
*/
$num = $this->size + $this->max_ch;
$this->ind = array($num);
for ($i1 = 0; $i1 < $num; $i1++)
$this->ind[$i1] = array($this->max_len);
$this->edge = array($this->max_len);
for ($i1 = 0; $i1 < $this->max_len; $i1++)
$this->edge[$i1] = array(5);
$this->pi = array($num);
$this->ro = array($num);
$this->len = array($num);
$this->kou1 = array($this->max_len);
$this->kou2 = array($this->max_len);
$this->s_w = array($num);
$this->pi_w = array($num);
/*
乱数の初期設定
*/
mt_srand($seed);
}
/**************************************************/
/* 場所を探す */
/* n : >=0 : n番目の親を捜す */
/* -1 : 空いている場所を探す */
/* return : 親の場所，または，空いている場所 */
/* （存在しないときは負の値） */
/**************************************************/
function Position($n)
{
$k = -1;
$sw = 0;
/*
空いている場所を探す
*/
if ($n < 0) {
for ($i1 = 0; $i1 < $this->size+$this->max_ch && $k < 0; $i1++) {
if ($this->pi_w[$i1] == 0)
$k = $i1;
}
if ($k < 0)
exit("***error 空いている場所がない --Position--\n");
}
/*
ｎ番目の親（$this->pi_w[i]=2）を捜す
*/
else {
for ($i1 = 0; $i1 < $this->size+$this->max_ch && $sw == 0; $i1++) {
if ($this->pi_w[$i1] == 2) {
$k++;
if ($k == $n) {
$sw = 1;
$k = $i1;
}
}
}
}
return $k;
}
/*******************************************************************/
/* 個体の選択 */
/* method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* bias : α，または，method=2の場合は初期値(default=0) */
/* step : β(default=1) */
/* return : 個体番号 */
/*******************************************************************/
function Select($method = -1, $bias = 0.0, $step = 1.0)
{
$sum = 0.0;
// ルーレット板の用意
switch ($method) {
// ランダム
case -1:
$n = 0;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1)
$n++;
}
$sum = 1.0 / $n;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1)
$this->ro[$i1] = $sum;
}
break;
// 評価値をそのまま利用
case 0:
$n = 0;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1) {
$sum += $this->pi[$i1];
$n++;
}
}
if (abs($sum) > 1.0e-10) {
$sum = 1.0 / abs($sum);
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1)
$this->ro[$i1] = $this->pi[$i1] * $sum;
}
}
else {
$sum = 1.0 / $n;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1)
$this->ro[$i1] = $sum;
}
}
break;
// 最小値からの差
case 1:
$min = -1;
$n = 0;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1) {
$n++;
if ($min < 0 || $this->pi[$i1] < $this->pi[$min])
$min = $i1;
}
}
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1) {
$this->ro[$i1] = $this->pi[$i1] - $this->pi[$min];
if ($this->ro[$i1] < $bias)
$this->ro[$i1] = $bias;
$sum += $this->ro[$i1];
}
}
if ($sum > 1.0e-10) {
$sum = 1.0 / $sum;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1)
$this->ro[$i1] *= $sum;
}
}
else {
$sum = 1.0 / $n;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1)
$this->ro[$i1] = $sum;
}
}
break;
// 線形化
case 2:
$n = 0;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1) {
$this->ro[$i1] = -1.0;
$n++;
}
else
$this->ro[$i1] = 1.0;
}
$sw = 0;
$sum = $bias;
while ($sw == 0) {
$min = -1;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->ro[$i1] < 0.0 && ($min < 0 || $this->pi[$i1] < $this->pi[$min]))
$min = $i1;
}
if ($min < 0)
$sw = 1;
else {
$this->ro[$min] = $sum;
$sum += $step;
}
}
$sum = 1.0 / (0.5 * (2.0 * $bias + $step * ($n - 1)) * $n);
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1)
$this->ro[$i1] *= $sum;
}
break;
}
$sum = 0.0;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1) {
$sum += $this->ro[$i1];
$this->ro[$i1] = $sum;
}
}
// 選択
$x = uniform();
$sw = 0;
$k = 0;
for ($i1 = 0; $i1 < $this->size+$this->max_ch && $sw == 0; $i1++) {
if ($this->pi_w[$i1] > 1) {
if ($x <= $this->ro[$i1]) {
$sw = 1;
$k = $i1;
}
}
}
return $k;
}
/********************/
/* 標準的な初期設定 */
/********************/
function Init_std()
{
/*
初期設定
*/
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($i1 < $this->size)
$this->pi_w[$i1] = 1; // 適応度の計算前
else
$this->pi_w[$i1] = 0; // 未使用
}
/*
遺伝子の決定
*/
for ($i1 = 0; $i1 < $this->size; $i1++) {
$sw1 = 0;
while ($sw1 == 0) {
// 遺伝子長の決定
if ($this->min_len < 0)
$length = $this->max_len;
else {
$length = intval(uniform() * ($this->max_len - $this->min_len + 1) + $this->min_len);
if ($length > $this->max_len)
$length = $this->max_len;
}
$this->len[$i1] = $length;
// 遺伝子の決定
for ($i2 = 0; $i2 < $length; $i2++) {
$sw2 = 0;
while ($sw2 == 0) {
$lid = intval(uniform() * ($this->allele_u - $this->allele_l + 1) + $this->allele_l);
if ($lid > $this->allele_u)
$lid = $this->allele_u;
$this->ind[$i1][$i2] = $lid;
// 重複遺伝子のチェック
$sw2 = 1;
if ($this->dup_a == 0) {
for ($i3 = 0; $i3 < $i2 && $sw2 > 0; $i3++) {
if ($lid == $this->ind[$i1][$i3])
$sw2 = 0;
}
}
}
}
// 重複個体のチェック
$sw1 = 1;
if ($this->dup_s == 0) {
for ($i2 = 0; $i2 < $i1 && $sw1 > 0; $i2++) {
if ($this->len[$i1] == $this->len[$i2]) {
$sw2 = 0;
for ($i3 = 0; $i3 < $this->len[$i1] && $sw2 == 0; $i3++) {
if ($this->ind[$i1][$i3] != $this->ind[$i2][$i3])
$sw2 = 1;
}
if ($sw2 == 0)
$sw1 = 0;
}
}
}
}
}
}
/****************************************************/
/* 標準的な出力 */
/* sw : 出力レベル */
/* =0 : 最終出力だけ */
/* n>0 : ｎ世代毎に出力（負はファイル） */
/* out_m : 出力方法 */
/* =0 : すべての個体を出力 */
/* =1 : 最大適応度の個体だけを出力 */
/* gen : 現在の世代番号 */
/* name : 出力ファイル名 */
/****************************************************/
function Out_std($sw, $out_m, $gen, $name)
{
$k = 0;
if ($sw >= 0) {
printf(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ ");
fscanf(STDIN, "%d", $pr);
}
else
$pr = -1;
if ($pr != 0) {
// 出力先の決定と評価値の出力
if ($pr > 0) {
$out = STDOUT;
fgets(STDIN);
}
else {
$x = getdate();
$now = $x["hours"]."時".$x["minutes"]."分".$x["seconds"]."秒";
$out = fopen($name, "ab");
fwrite($out, "***世代 ".$gen." 適応度 max ".$this->max." (".$this->max_n.") mean ".$this->mean." 時間 ".$now."\n");
}
// 詳細出力
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if (($this->pi_w[$i1] > 1) && ($out_m == 0 || $out_m == 1 && $i1 == $this->max_n)) {
$str = $i1." allele";
for ($i2 = 0; $i2 < $this->len[$i1]; $i2++)
$str += " ".$this->ind[$i1][$i2];
$str += " value ".$this->pi[$i1];
fwrite($out, $str."\n");
if ($pr > 0) {
$k++;
if ($k == $pr) {
fgets(STDIN);
$k = 0;
}
}
}
}
if ($pr < 0)
fclose($out);
}
}
/*******************************************************************/
/* 交叉（親のコピー） */
/* method : =2 : 有性（２つの親から２つの子供）(default) */
/* =1 : １つの親から１つの子供 */
/* pair : method=2 の時は親のペア数(default=max_ch/2) */
/* method=1 の時は親の数（＝子供の数） */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_copy($method = 2, $pair = 0, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
/*
初期設定とデータチェック
*/
if ($method != 1)
$method = 2;
if ($pair <= 0)
$pair = ($method==2) ? intval($this->max_ch/2) : $this->max_ch;
else {
if ($method == 2 && 2*$pair > $this->max_ch || $method == 1 && $pair > $this->max_ch)
exit("***error 子供が多すぎる (C_copy)\n");
}
/*
実行
*/
for ($i1 = 0; $i1 < $pair; $i1++) {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// コピー
for ($i2 = 0; $i2 < $method; $i2++) {
$p = ($i2 == 0) ? $p1 : $p2;
$k = $this->Position(-1);
$this->len[$k] = $this->len[$p];
$this->pi_w[$k] = 1;
for ($i3 = 0; $i3 < $this->len[$k]; $i3++)
$this->ind[$k][$i3] = $this->ind[$p][$i3];
}
}
}
/*******************************************************************/
/* 交叉（多点交叉） */
/* kosa : 交叉確率 */
/* k_point : 交叉点の数(default=1) */
/* （負の時は，1から-k_point間のランダム） */
/* k_vr : =0 : 両親とも同じ位置で交叉(default) */
/* =1 : 両親が異なる位置で交叉（遺伝子長は可変） */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_point($kosa, $k_point = 1, $k_vr = 0, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
$mn = 0;
/*
初期設定とデータのチェック
*/
$pair = $this->max_ch / 2;
if ($this->dup_a == 0)
exit("***error 交叉方法が不適当 (C_point)\n");
$abs_p = abs($k_point);
if ($abs_p == 0 || $abs_p > $this->max_len-1 || $this->min_len > 0 && $abs_p > $this->min_len-1)
exit("***error 交叉点の数が不適当 (C_point)\n");
if ($k_vr > 0 && $this->min_len < 0)
exit("***error 遺伝子長は可変でなければならない (C_point)\n");
/*
交叉
*/
$num = $k_point;
for ($i1 = 0; $i1 < $pair; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(2, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 交叉位置の数の決定
if ($k_point < 0) {
$num = intval(uniform() * $abs_p + 1);
if ($num > $abs_p)
$num = $abs_p;
}
// 交叉位置の決定（点の後ろで交叉）
for ($i2 = 0; $i2 < $num; $i2++) {
// 親１の交叉位置
$sw = 0;
while ($sw == 0) {
$sw = 1;
$this->kou1[$i2] = intval(uniform() * ($this->len[$p1] - 1));
if ($this->kou1[$i2] > $this->len[$p1]-2)
$this->kou1[$i2] = $this->len[$p1] - 2;
if ($k_vr == 0 && $this->kou1[$i2] > $this->len[$p2]-2)
$this->kou1[$i2] = $this->len[$p2] - 2;
for ($i3 = 0; $i3 < $i2 && $sw > 0; $i3++) {
if ($this->kou1[$i3] == $this->kou1[$i2])
$sw = 0;
}
}
// 親２の交叉位置
if ($k_vr > 0) {
$sw = 0;
while ($sw == 0) {
$sw = 1;
$this->kou2[$i2] = intval(uniform() * ($this->len[$p2] - 1));
if ($this->kou2[$i2] > $this->len[$p2]-2)
$this->kou2[$i2] = $this->len[$p2] - 2;
for ($i3 = 0; $i3 < $i2 && $sw > 0; $i3++) {
if ($this->kou2[$i3] == $this->kou2[$i2])
$sw = 0;
}
}
}
}
// 交叉の実行
// 親１のt11からt12を子１のc1へコピー
// 親２のt21からt22を子２のc2へコピー
// 次は，
// 親１のt11からt12を子２のc2へコピー
// 親２のt21からt22を子１のc1へコピー
// ・・・・・
$c1 = 0;
$c2 = 0;
$t11 = 0;
$t21 = 0;
// 遺伝子長
$k1 = $this->Position(-1);
$this->pi_w[$k1] = 1;
$this->len[$k1] = $this->len[$p1];
$k2 = $this->Position(-1);
$this->pi_w[$k2] = 1;
$this->len[$k2] = $this->len[$p2];
for ($i2 = 0; $i2 < $num+1; $i2++ ) {
// 次の交叉位置を求める
if ($i2 == $num) { // 最後
$t12 = $this->len[$p1];
$t22 = $this->len[$p2];
}
else {
// 親１
$t12 = $this->max_len;
for ($i3 = 0; $i3 < $num; $i3++) {
if ($this->kou1[$i3] >= 0 && $this->kou1[$i3] <= $t12) {
$t12 = $this->kou1[$i3];
$mn = $i3;
}
}
$this->kou1[$mn] = -1;
$t12++;
// 親２
if ($k_vr == 0)
$t22 = $t12;
else {
$t22 = $this->max_len;
for ($i3 = 0; $i3 < $num; $i3++) {
if ($this->kou2[$i3] >= 0 && $this->kou2[$i3] <= $t22) {
$t22 = $this->kou2[$i3];
$mn = $i3;
}
}
$this->kou2[$mn] = -1;
$t22++;
}
}
// 指定箇所のコピー
for ($i3 = $t11; $i3 < $t12; $i3++) {
if ($i2%2 == 0) {
if ($c1 < $this->max_len) {
$this->ind[$k1][$c1] = $this->ind[$p1][$i3];
$c1++;
}
}
else {
if ($c2 < $this->max_len) {
$this->ind[$k2][$c2] = $this->ind[$p1][$i3];
$c2++;
}
}
}
for ($i3 = $t21; $i3 < $t22; $i3++) {
if ($i2%2 == 0) {
if ($c2 < $this->max_len) {
$this->ind[$k2][$c2] = $this->ind[$p2][$i3];
$c2++;
}
}
else {
if ($c1 < $this->max_len) {
$this->ind[$k1][$c1] = $this->ind[$p2][$i3];
$c1++;
}
}
}
// 交叉位置の移動
$t11 = $t12;
$t21 = $t22;
}
}
}
}
/*******************************************************************/
/* 交叉（一様交叉．[0,1]を等確率で発生させ，1であれば， */
/* 親１，0であれば親２の遺伝子を子１が受け継ぐ） */
/* kosa : 交叉確率 */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_uniform($kosa, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
/*
初期設定とデータのチェック
*/
$pair = $this->max_ch / 2;
if ($this->dup_a == 0)
exit("***error 交叉方法が不適当 (C_uniform)\n");
if ($this->min_len > 0)
exit("***error 遺伝子長は固定長でなければならない (C_uniform)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $pair; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(2, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 遺伝子長
$k1 = $this->Position(-1);
$this->pi_w[$k1] = 1;
$this->len[$k1] = $this->len[$p1];
$k2 = $this->Position(-1);
$this->pi_w[$k2] = 1;
$this->len[$k2] = $this->len[$p2];
// 交叉
for ($i2 = 0; $i2 < $this->len[$p1]; $i2++) {
if (uniform() > 0.5) {
$this->ind[$k1][$i2] = $this->ind[$p1][$i2];
$this->ind[$k2][$i2] = $this->ind[$p2][$i2];
}
else {
$this->ind[$k1][$i2] = $this->ind[$p2][$i2];
$this->ind[$k2][$i2] = $this->ind[$p1][$i2];
}
}
}
}
}
/*******************************************************************/
/* 交叉（平均化交叉．２つの親の平均値を受け継ぐ） */
/* kosa : 交叉確率 */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_mean($kosa, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
/*
初期設定とデータのチェック
*/
if ($this->min_len > 0)
exit("***error 遺伝子長は固定長でなければならない (C_mean)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $this->max_ch; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(1, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 遺伝子長
$k = $this->Position(-1);
$this->len[$k] = $this->len[$p1];
$this->pi_w[$k] = 1;
// 交叉
for ($i2 = 0; $i2 < $this->len[$k]; $i2++)
$this->ind[$k][$i2] = ($this->ind[$p1][$i2] + $this->ind[$p2][$i2]) / 2;
}
}
}
/*******************************************************************/
/* 交叉（循環交叉．ランダムに１点を選択し，その位置にある遺伝子を */
/* そのまま各子供が選択する．その位置にある親２（１）の遺伝 */
/* 子を，その遺伝子の親１（２）の場所に，子１（２）が受け継 */
/* ぐ（ただし，doubleの場合は，この手続きをのぞく）．この手 */
/* 続きを，すでに受け継いだ遺伝子の位置が選択されるまで繰り */
/* 返し，残りの遺伝子については，子１（２）は，親２（１）の */
/* 遺伝子をその順番通りに受け継ぐ） */
/* 2 4 1 3 6 5 + + 1 + + 5 3 2 1 4 6 5 */
/* * → → */
/* 3 2 5 4 1 6 + + 5 + 1 + 2 4 5 3 1 6 */
/* kosa : 交叉確率 */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_cycle($kosa, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
/*
初期設定とデータのチェック
*/
$pair = $this->max_ch / 2;
if ($this->dup_a != 0)
exit("***error 交叉方法が不適当 (C_cycle)\n");
if ($this->min_len > 0)
exit("***error 遺伝子長は固定長でなければならない (C_cycle)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $pair; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(2, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 初期設定
for ($i2 = 0; $i2 < $this->len[$p1]; $i2++) {
$this->kou1[$i2] = 0;
$this->kou2[$i2] = 0;
}
// 遺伝子長
$k1 = $this->Position(-1);
$this->pi_w[$k1] = 1;
$this->len[$k1] = $this->len[$p1];
$k2 = $this->Position(-1);
$this->pi_w[$k2] = 1;
$this->len[$k2] = $this->len[$p2];
// 交叉
$sw = 0;
while ($sw == 0) {
$sw = 1;
$p = intval(uniform() * $this->len[$p1]);
if ($p >= $this->len[$p1])
$p = $this->len[$p1] - 1;
if ($this->kou1[$p] == 0 && $this->kou2[$p] == 0) {
$this->kou1[$p] = 1;
$this->kou2[$p] = 1;
$this->ind[$k1][$p] = $this->ind[$p1][$p];
$this->ind[$k2][$p] = $this->ind[$p2][$p];
for ($i2 = 0; $i2 < $this->len[$p1] && $sw > 0; $i2++) {
if ($this->ind[$p2][$p] == $this->ind[$p1][$i2]) {
$this->ind[$k1][$i2] = $this->ind[$p1][$i2];
$this->kou1[$i2] = 1;
$sw = 0;
}
}
$sw = 1;
for ($i2 = 0; $i2 < $this->len[$p2] && $sw > 0; $i2++) {
if ($this->ind[$p1][$p] == $this->ind[$p2][$i2]) {
$this->ind[$k2][$i2] = $this->ind[$p2][$i2];
$this->kou2[$i2] = 1;
$sw = 0;
}
}
}
}
$sw = 0;
$i2 = 0;
$i3 = 0;
while ($sw == 0) {
while ($sw == 0 && $i2 < $this->len[$p1]) {
if ($this->kou1[$i2] == 0)
$sw = 1;
else
$i2++;
}
$sw = 0;
while ($sw == 0 && $i3 < $this->len[$p2]) {
if ($this->kou2[$i3] == 0)
$sw = 1;
else
$i3++;
}
if ($i2 < $this->len[$p1] && $i3 < $this->len[$p2]) {
$this->ind[$k1][$i2] = $this->ind[$p2][$i3];
$this->ind[$k2][$i3] = $this->ind[$p1][$i2];
$sw = 0;
$i2++;
$i3++;
}
else
$sw = 1;
}
}
}
}
/*******************************************************************/
/* 交叉（部分的交叉．ランダムに１点を選択し，その位置にある親１と */
/* 親２の遺伝子を取り出す．次に，親１と親２の染色体上で，こ */
/* の２つの遺伝子の位置を交換する．この操作を，選択した点よ */
/* り右にあるすべての遺伝子に対して実施する */
/* 2 4 1 3 6 5 2 4 5 3 6 1 */
/* * → → ･････ */
/* 3 2 5 4 1 6 3 2 1 4 5 6 */
/* kosa : 交叉確率 */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_part($kosa, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
/*
初期設定とデータのチェック
*/
$pair = $this->max_ch / 2;
if ($this->dup_a != 0)
exit("***error 交叉方法が不適当 (C_part)\n");
if ($this->min_len > 0)
exit("***error 遺伝子長は固定長でなければならない (C_part)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $pair; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(2, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 遺伝子長
$k1 = $this->Position(-1);
$this->pi_w[$k1] = 1;
$this->len[$k1] = $this->len[$p1];
$k2 = $this->Position(-1);
$this->pi_w[$k2] = 1;
$this->len[$k2] = $this->len[$p2];
// 交叉
$p = intval(uniform() * $this->len[$p1]);
if ($p >= $this->len[$p1])
$p = $this->len[$p1] - 1;
for ($i2 = 0; $i2 < $this->len[$p1]; $i2++) {
$this->ind[$k1][$i2] = $this->ind[$p1][$i2];
$this->ind[$k2][$i2] = $this->ind[$p2][$i2];
}
for ($i2 = $p; $i2 < $this->len[$p1]; $i2++) {
$sw = 0;
$lv = $this->ind[$k1][$i2];
for ($i3 = 0; $i3 < $this->len[$p1] && $sw == 0; $i3++) {
if ($this->ind[$k2][$i2] == $this->ind[$k1][$i3]) {
$this->ind[$k1][$i2] = $this->ind[$k1][$i3];
$this->ind[$k1][$i3] = $lv;
$sw = 1;
}
}
$sw = 0;
for ($i3 = 0; $i3 < $this->len[$p1] && $sw == 0; $i3++) {
if ($lv == $this->ind[$k2][$i3]) {
$this->ind[$k2][$i3] = $this->ind[$k2][$i2];
$this->ind[$k2][$i2] = $lv;
$sw = 1;
}
}
}
}
}
}
/*******************************************************************/
/* 交叉（順序交叉．ランダムに切れ目を決定し，子１に対し，切れ目の */
/* 左側では，親１の遺伝子をそのまま受け継ぎ，右側では，親１ */
/* の遺伝子を親２の遺伝子の出現順序に並べ替える． */
/* 2 4 1 3 6 5 2 4 1 3 5 6 */
/* * → */
/* 3 2 5 4 1 6 3 2 5 4 1 6 */
/* kosa : 交叉確率 */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_seq($kosa, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
/*
初期設定とデータのチェック
*/
$pair = $this->max_ch / 2;
if ($this->dup_a != 0)
exit("***error 交叉方法が不適当 (C_seq)\n");
if ($this->min_len > 0)
exit("***error 遺伝子長は固定長でなければならない (C_seq)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $pair; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(2, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 遺伝子長
$k1 = $this->Position(-1);
$this->pi_w[$k1] = 1;
$this->len[$k1] = $this->len[$p1];
$k2 = $this->Position(-1);
$this->pi_w[$k2] = 1;
$this->len[$k2] = $this->len[$p2];
// 交叉
$p = intval(uniform() * ($this->len[$p1] - 1));
if ($p >= $this->len[$p1]-1)
$p = $this->len[$p1] - 2;
for ($i2 = 0; $i2 <= $p; $i2++) {
$this->ind[$k1][$i2] = $this->ind[$p1][$i2];
$this->ind[$k2][$i2] = $this->ind[$p2][$i2];
}
$pp = 0;
for ($i2 = $p+1; $i2 < $this->len[$p1]; $i2++) {
$sw = 0;
for ($i3 = $pp; $i3 < $this->len[$p2] && $sw == 0; $i3++) {
for ($i4 = $p+1; $i4 < $this->len[$p1] && $sw == 0; $i4++) {
if ($this->ind[$p2][$i3] == $this->ind[$p1][$i4]) {
$sw = 1;
$pp = $i3 + 1;
$this->ind[$k1][$i2] = $this->ind[$p1][$i4];
}
}
}
}
$pp = 0;
for ($i2 = $p+1; $i2 < $this->len[$p2]; $i2++) {
$sw = 0;
for ($i3 = $pp; $i3 < $this->len[$p1] && $sw == 0; $i3++) {
for ($i4 = $p+1; $i4 < $this->len[$p2] && $sw == 0; $i4++) {
if ($this->ind[$p1][$i3] == $this->ind[$p2][$i4]) {
$sw = 1;
$pp = $i3 + 1;
$this->ind[$k2][$i2] = $this->ind[$p2][$i4];
}
}
}
}
}
}
}
/*******************************************************************/
/* 交叉（一様順序交叉．位置の集合をランダムに選択し，一方の親の選 */
/* 択された位置における遺伝子の順序に従って，他の親の遺伝子 */
/* を並べ替える */
/* 2 4 1 3 6 5 2 4 1 3 6 5 */
/* * * → */
/* 3 2 5 4 1 6 4 2 5 3 1 6 */
/* kosa : 交叉確率 */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_useq($kosa, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
/*
初期設定とデータのチェック
*/
$pair = $this->max_ch / 2;
if ($this->dup_a != 0)
exit("***error 交叉方法が不適当 (C_useq)\n");
if ($this->min_len > 0)
exit("***error 遺伝子長は固定長でなければならない (C_useq)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $pair; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(2, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 遺伝子長
$k1 = $this->Position(-1);
$this->pi_w[$k1] = 1;
$this->len[$k1] = $this->len[$p1];
$k2 = $this->Position(-1);
$this->pi_w[$k2] = 1;
$this->len[$k2] = $this->len[$p2];
// 交叉
for ($i2 = 0; $i2 < $this->len[$p1]; $i2++) {
$this->ind[$k1][$i2] = $this->ind[$p1][$i2];
$this->ind[$k2][$i2] = $this->ind[$p2][$i2];
$this->kou1[$i2] = (uniform() < 0.5) ? 0 : 1;
}
$p = 0;
for ($i2 = 0; $i2 < $this->len[$p1]; $i2++) {
if ($this->kou1[$i2] > 0) {
$sw = 0;
for ($i3 = $p; $i3 < $this->len[$p2] && $sw == 0; $i3++) {
for ($i4 = 0; $i4 < $this->len[$p1] && $sw == 0; $i4++) {
if ($this->ind[$p2][$i3] == $this->ind[$p1][$i4] && $this->kou1[$i4] > 0) {
$sw = 1;
$p = $i3 + 1;
$this->ind[$k1][$i2] = $this->ind[$p1][$i4];
}
}
}
}
}
$p = 0;
for ($i2 = 0; $i2 < $this->len[$p2]; $i2++) {
if ($this->kou1[$i2] > 0) {
$sw = 0;
for ($i3 = $p; $i3 < $this->len[$p1] && $sw == 0; $i3++) {
for ($i4 = 0; $i4 < $this->len[$p2] && $sw == 0; $i4++) {
if ($this->ind[$p1][$i3] == $this->ind[$p2][$i4] && $this->kou1[$i4] > 0) {
$sw = 1;
$p = $i3 + 1;
$this->ind[$k2][$i2] = $this->ind[$p2][$i4];
}
}
}
}
}
}
}
}
/*******************************************************************/
/* 交叉（一様位置交叉．位置の集合をランダムに選択し，一方の親の選 */
/* 択された位置における遺伝子の位置に，他の親の同じ遺伝子を */
/* 配置する．残りの遺伝子は，親と同じ順序に配置する． */
/* 2 4 1 3 6 5 + + 5 + 1 + 2 4 5 3 1 6 */
/* * * → → */
/* 3 2 5 4 1 6 + + 1 + 6 + 3 2 1 5 6 4 */
/* kosa : 交叉確率 */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_upos($kosa, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
/*
初期設定とデータのチェック
*/
$pair = $this->max_ch / 2;
if ($this->dup_a != 0)
exit("***error 交叉方法が不適当 (C_upos)\n");
if ($this->min_len > 0)
exit("***error 遺伝子長は固定長でなければならない (C_upos)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $pair; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(2, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 遺伝子長
$k1 = $this->Position(-1);
$this->pi_w[$k1] = 1;
$this->len[$k1] = $this->len[$p1];
$k2 = $this->Position(-1);
$this->pi_w[$k2] = 1;
$this->len[$k2] = $this->len[$p2];
// 交叉
for ($i2 = 0; $i2 < $this->len[$p1]; $i2++) {
$this->kou1[$i2] = (uniform() < 0.5) ? 0 : 1;
if ($this->kou1[$i2] > 0) {
$this->ind[$k1][$i2] = $this->ind[$p2][$i2];
$this->ind[$k2][$i2] = $this->ind[$p1][$i2];
}
}
$p = 0;
for ($i2 = 0; $i2 < $this->len[$p1]; $i2++) {
$sw = 0;
for ($i3 = 0; $i3 < $this->len[$p1] && $sw == 0; $i3++) {
if ($this->kou1[$i3] > 0 && $this->ind[$p1][$i2] == $this->ind[$k1][$i3])
$sw = 1;
}
if ($sw == 0) {
for ($i3 = $p; $i3 < $this->len[$p1] && $sw == 0; $i3++) {
if ($this->kou1[$i3] == 0) {
$this->ind[$k1][$i3] = $this->ind[$p1][$i2];
$p = $i3 + 1;
$sw = 1;
}
}
}
}
$p = 0;
for ($i2 = 0; $i2 < $this->len[$p2]; $i2++) {
$sw = 0;
for ($i3 = 0; $i3 < $this->len[$p2] && $sw == 0; $i3++) {
if ($this->kou1[$i3] > 0 && $this->ind[$p2][$i2] == $this->ind[$k2][$i3])
$sw = 1;
}
if ($sw == 0) {
for ($i3 = $p; $i3 < $this->len[$p2] && $sw == 0; $i3++) {
if ($this->kou1[$i3] == 0) {
$this->ind[$k2][$i3] = $this->ind[$p2][$i2];
$p = $i3 + 1;
$sw = 1;
}
}
}
}
}
}
}
/*******************************************************************/
/* 交叉（エッジ組み替え交叉．以下の手順に従って行う．対立遺伝子は */
/* 0～(max_len-1)である必要がある） */
/* (0) エッジマップを作成する．エッジマップとは，２つの親 */
/* を見て，ノードがどこに接続されているのかを表すもの */
/* であり，例えば，２つの親が， */
/* [A B C D E F] */
/* [B D C A E F] */
/* である場合は， */
/* A : B F C E */
/* B : A C D F */
/* C : B D A */
/* D : C E B */
/* E : D F A */
/* F : A E B */
/* となる． */
/* (1) 両親の２つの出発点の内１つで初期化する．ランダムま */
/* たはステップ(4)の基準に従って選ぶ（現在のノード） */
/* (2) エッジマップから，現在のノードを除く */
/* (3) 現在のノードが接続先のノードを持っていたら，(4)に */
/* 進む．さもなければ，(5)に進む */
/* (4) 現在のノードが持っている接続先ノードの内，最も少な */
/* い接続先ノードを持ったノードを選択し（同じ条件の場 */
/* 合は，ランダム），それを現在のノードとし，(2)に進む */
/* (5) 未接続のノードが残っていればランダムに選択し，(2)に */
/* 戻る．さもなければ，終了する */
/* kosa : 交叉確率 */
/* k_method : 選択方法 */
/* =-1 : ランダム(default) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* k_bias : α，または，method=2の場合は初期値(default=0) */
/* k_step : β(default=1) */
/*******************************************************************/
function C_edge($kosa, $k_method = -1, $k_bias = 0.0, $k_step = 1.0)
{
$e = array(2);
$k0 = 0;
/*
初期設定とデータのチェック
*/
$pair = $this->max_ch;
if ($this->dup_a != 0)
exit("***error 交叉方法が不適当 (C_edge)\n");
if ($this->min_len > 0)
exit("***error 遺伝子長は固定長でなければならない (C_edge)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $pair; $i1++) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(1, 1);
// 交叉する場合
else {
// 親の選択
$p1 = $this->Select($k_method, $k_bias, $k_step);
$sw = 0;
while ($sw == 0) {
$p2 = $this->Select($k_method, $k_bias, $k_step);
if ($p1 != $p2)
$sw = 1;
}
// 遺伝子長
$k = $this->Position(-1);
$this->pi_w[$k] = 1;
$this->len[$k] = $this->len[$p1];
// エッジマップの初期化
for ($i2 = 0; $i2 < $this->len[$k]; $i2++) {
$this->edge[$i2][0] = 0;
for ($i3 = 1; $i3 <= 4; $i3++)
$this->edge[$i2][$i3] = -1;
}
// 交叉
// エッジマップの作成
for ($i2 = 0; $i2 < $this->len[$k]; $i2++) {
$sw = 0;
for ($i3 = 0; $i3 < $this->len[$k] && $sw == 0; $i3++) {
if ($i2 == $this->ind[$p1][$i3]) {
$sw = 1;
if ($i3 == 0) {
$e[0] = $this->ind[$p1][$this->len[$k]-1];
$e[1] = $this->ind[$p1][1];
}
else {
if ($i3 == $this->len[$k]-1) {
$e[0] = $this->ind[$p1][$i3-1];
$e[1] = $this->ind[$p1][0];
}
else {
$e[0] = $this->ind[$p1][$i3-1];
$e[1] = $this->ind[$p1][$i3+1];
}
}
for ($i4 = 0; $i4 < 2; $i4++) {
$this->edge[$i2][0]++;
$this->edge[$i2][$this->edge[$i2][0]] = $e[$i4];
}
}
}
$sw = 0;
for ($i3 = 0; $i3 < $this->len[$k] && $sw == 0; $i3++) {
if ($i2 == $this->ind[$p2][$i3]) {
$sw = 1;
if ($i3 == 0) {
$e[0] = $this->ind[$p2][$this->len[$k]-1];
$e[1] = $this->ind[$p2][1];
}
else {
if ($i3 == $this->len[$k]-1) {
$e[0] = $this->ind[$p2][$i3-1];
$e[1] = $this->ind[$p2][0];
}
else {
$e[0] = $this->ind[$p2][$i3-1];
$e[1] = $this->ind[$p2][$i3+1];
}
}
for ($i4 = 0; $i4 < 2; $i4++) {
$sw = 1;
for ($i5 = 1; $i5 <= $this->edge[$i2][0] && $sw == 1; $i5++) {
if ($this->edge[$i2][$i5] == $e[$i4])
$sw = 2;
}
if ($sw == 1) {
$this->edge[$i2][0]++;
$this->edge[$i2][$this->edge[$i2][0]] = $e[$i4];
}
}
}
}
}
// 交叉の実行
// 出発点の決定
$k1 = $this->ind[$p1][0];
$k2 = $this->ind[$p2][0];
if ($this->edge[$k1][0] == $this->edge[$k2][0])
$kk = (uniform() > 0.5) ? $k2 : $k1;
else
$kk = ($this->edge[$k1][0] < $this->edge[$k2][0]) ? $k1 : $k2;
$this->ind[$k][0] = $kk;
$p = 1;
while ($p < $this->len[$k]) {
// ノードの除去
for ($i2 = 0; $i2 < $this->len[$k]; $i2++) {
$sw = 0;
if ($this->edge[$i2][0] > 0) {
for ($i3 = 1; $i3 <= 4 && $sw == 0; $i3++) {
if ($this->edge[$i2][$i3] == $kk) {
$sw = 1;
$this->edge[$i2][$i3] = -1;
$this->edge[$i2][0]--;
}
}
}
}
// 次の現在ノードの選択
$min = 10;
$num = 0;
for ($i2 = 1; $i2 <= 4; $i2++) {
if ($this->edge[$kk][$i2] >= 0) {
$k1 = $this->edge[$kk][$i2];
if ($this->edge[$k1][0] >= 0 && $this->edge[$k1][0] < $min) {
$num = 1;
$min = $this->edge[$k1][0];
$k0 = $k1;
}
else {
if ($this->edge[$k1][0] == $min)
$num++;
}
}
}
if ($num > 1) {
$k1 = intval(uniform() * $num) + 1;
if ($k1 > $num)
$k1 = $num;
$k2 = 0;
$k0 = -1;
for ($i2 = 1; $i2 <= 4 && $k0 < 0; $i2++) {
if ($this->edge[$kk][$i2] >= 0) {
if ($this->edge[$this->edge[$kk][$i2]][0] == $min) {
$k2++;
if ($k1 == $k2)
$k0 = $this->edge[$kk][$i2];
}
}
}
}
else {
if ($num <= 0) {
$num = 0;
for ($i2 = 0; $i2 < $this->len[$k]; $i2++) {
if ($i2 != $kk && $this->edge[$i2][0] >= 0)
$num++;
}
if ($num <= 0)
exit("***error invalid data (C_edge)\n");
else {
$k1 = intval(uniform() * $num) + 1;
if ($k1 > $num)
$k1 = $num;
$k2 = 0;
$k0 = -1;
for ($i2 = 0; $i2 < $this->len[$k] && $k0 < 0; $i2++) {
if ($i2 != $kk && $this->edge[$i2][0] >= 0) {
$k2++;
if ($k1 == $k2)
$k0 = $i2;
}
}
}
}
}
$this->edge[$kk][0] = -1;
$this->ind[$k][$p] = $k0;
$kk = $k0;
$p++;
}
}
}
}
/*************************************************************/
/* 交叉（サブツアー交叉．２点交叉の拡張である．ただし，相手に*/
/* 同じ遺伝子のグループがない限り実行されない．たとえば*/
/* ***abcd** */
/* *cdab**** */
/* のような両親の時実行され，以下の４つの子供が生成され*/
/* る） */
/* ***cdab** */
/* *abcd**** */
/* ***badc** */
/* *dcba**** */
/* 最大，４＊交叉回数＊個体総数＊(個体総数－１) 個の子 */
/* 供が生成される可能性があるので，子供の数としてこの値*/
/* 以上のデータを入力しておく必要がある． */
/* kosa : 交叉確率 */
/* count : １つのペアーに対する交差回数(default=10) */
/*************************************************************/
function C_sub($kosa, $count = 10)
{
$t22 = 0;
/*
初期設定とデータのチェック
*/
if ((4*$count*$this->size*($this->size-1)) > $this->max_ch)
exit("***error 子供が多すぎる (C_sub)\n");
/*
交叉
*/
for ($i1 = 0; $i1 < $this->size-1; $i1++) {
// 親１
$p1 = $this->Position($i1);
if ($p1 >= 0) {
for ($i2 = $i1; $i2 < $this->size; $i2++) {
// 親２
$p2 = $this->Position($i2);
if ($p2 >= 0) {
// 交叉しない場合
if (uniform() > $kosa)
$this->C_copy(2, 1);
// 交叉する場合
else {
// 交叉回数の制御
for ($i3 = 0; $i3 < $count; $i3++) {
// 交叉位置の決定（点の後ろで交叉）
// 親１の交叉位置
$t11 = intval(uniform() * $this->len[$p1]);
if ($t11 > ($this->len[$p1]-1))
$t11 = $this->len[$p1] - 1;
$sw = 0;
while ($sw == 0) {
$t12 = intval(uniform() * $this->len[$p1]);
if ($t12 > ($this->len[$p1]-1))
$t12 = $this->len[$p1] - 1;
if ($t12 != $t11)
$sw = 1;
}
if ($t11 > $t12) {
$k1 = $t11;
$t11 = $t12;
$t12 = $k1;
}
// 親２の交叉位置
$sw = 0;
$t21 = -1;
for ($i4 = 0; $i4 < $this->len[$p2] && $t21 < 0; $i4++) {
for ($i5 = $t11; $i5 <= $t12 && $t21 < 0; $i5++) {
if ($this->ind[$p2][$i4] == $this->ind[$p1][$i5])
$t21 = $i4;
}
}
if ($t21 >= 0) {
$t22 = $t21 + $t12 - $t11;
if ($t22 < $this->len[$p2]) {
$sw = 1;
for ($i4 = $t21+1; $i4 <= $t22 && $sw > 0; $i4++) {
$sw = 0;
for ($i5 = $t11; $i5 <= $t12 && $sw == 0; $i5++) {
if ($this->ind[$p2][$i4] == $this->ind[$p1][$i5])
$sw = 1;
}
}
}
}
// 交叉の実行
if ($sw > 0) {
$k1 = $this->Position(-1);
$this->pi_w[$k1] = 1;
$this->len[$k1] = $this->len[$p1];
$k2 = $this->Position(-1);
$this->pi_w[$k2] = 1;
$this->len[$k2] = $this->len[$p1];
$k3 = $this->Position(-1);
$this->pi_w[$k3] = 1;
$this->len[$k3] = $this->len[$p2];
$k4 = $this->Position(-1);
$this->pi_w[$k4] = 1;
$this->len[$k4] = $this->len[$p2];
for ($i4 = 0; $i4 < $t11; $i4++) {
$this->ind[$k1][$i4] = $this->ind[$p1][$i4];
$this->ind[$k2][$i4] = $this->ind[$p1][$i4];
}
for ($i4 = $t11; $i4 <= $t12; $i4++) {
$this->ind[$k1][$i4] = $this->ind[$p2][$t21+$i4-$t11];
$this->ind[$k2][$i4] = $this->ind[$p2][$t22-$i4+$t11];
}
for ($i4 = $t12+1; $i4 < $this->len[$p1]; $i4++) {
$this->ind[$k1][$i4] = $this->ind[$p1][$i4];
$this->ind[$k2][$i4] = $this->ind[$p1][$i4];
}
for ($i4 = 0; $i4 < $t21; $i4++) {
$this->ind[$k3][$i4] = $this->ind[$p2][$i4];
$this->ind[$k4][$i4] = $this->ind[$p2][$i4];
}
for ($i4 = $t21; $i4 <= $t22; $i4++) {
$this->ind[$k3][$i4] = $this->ind[$p1][$t11+$i4-$t21];
$this->ind[$k4][$i4] = $this->ind[$p1][$t12-$i4+$t21];
}
for ($i4 = $t22+1; $i4 < $this->len[$p2]; $i4++) {
$this->ind[$k3][$i4] = $this->ind[$p2][$i4];
$this->ind[$k4][$i4] = $this->ind[$p2][$i4];
}
}
}
}
}
}
}
}
}
/**************************************/
/* 突然変異（対立遺伝子との置き換え） */
/* pr : 突然変異率 */
/**************************************/
function M_alle($pr)
{
/*
データのチェックと初期設定
*/
if ($this->dup_a == 0)
exit("***error 突然変異方法が不適当 (M_alle)\n");
/*
実行
*/
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1) {
for ($i2 = 0; $i2 < $this->len[$i1]; $i2++) {
if (uniform() <= $pr) {
$lid = intval(uniform() * ($this->allele_u - $this->allele_l + 1) + $this->allele_l);
if ($lid > $this->allele_u)
$lid = $this->allele_u;
if ($lid != $this->ind[$i1][$i2])
$this->ind[$i1][$i2] = $lid;
}
}
}
}
}
/**********************************************************************/
/* 突然変異（移動．２点を選択し，２番目の遺伝子を１番目の遺伝子の前に */
/* 移動する） */
/* pr : 突然変異率 */
/**********************************************************************/
function M_move($pr)
{
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1 && uniform() <= $pr) {
/*
位置の決定
*/
// p1
$p1 = intval(uniform() * $this->len[$i1]);
if ($p1 >= $this->len[$i1])
$p1 = $this->len[$i1] - 1;
// p2
$sw = 0;
while ($sw == 0) {
$p2 = intval(uniform() * $this->len[$i1]);
if ($p2 >= $this->len[$i1])
$p2 = $this->len[$i1] - 1;
if ($p2 != $p1)
$sw = 1;
}
/*
実行
*/
if ($p2 > $p1) {
$ld = $this->ind[$i1][$p2];
for ($i2 = $p2; $i2 > $p1; $i2--)
$this->ind[$i1][$i2] = $this->ind[$i1][$i2-1];
$this->ind[$i1][$p1] = $ld;
}
else {
$ld = $this->ind[$i1][$p2];
for ($i2 = $p2; $i2 < $p1-1; $i2++)
$this->ind[$i1][$i2] = $this->ind[$i1][$i2+1];
$this->ind[$i1][$p1-1] = $ld;
}
}
}
}
/********************************************************/
/* 突然変異（逆位．２点間の遺伝子順序を逆に並べ替える） */
/* pr : 突然変異率 */
/* wd : >0 : 幅を固定 */
/* =0 : 幅をランダム(default) */
/********************************************************/
function M_inv($pr, $wd = 0)
{
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1 && uniform() <= $pr) {
/*
区間の決定
*/
if ($wd == 0) {
$p1 = intval(uniform() * $this->len[$i1]);
if ($p1 >= $this->len[$i1])
$p1 = $this->len[$i1] - 1;
$sw = 0;
while ($sw == 0) {
$p2 = intval(uniform() * $this->len[$i1]);
if ($p2 >= $this->len[$i1])
$p2 = $this->len[$i1] - 1;
if ($p2 != $p1)
$sw = 1;
}
if ($p1 > $p2) {
$p = $p1;
$p1 = $p2;
$p2 = $p;
}
}
else {
$p1 = $this->len[$i1];
while ($p1 > $this->len[$i1]-2)
$p1 = intval(uniform() * $this->len[$i1]);
$p2 = $p1 + $wd - 1;
if ($p2 >= $this->len[$i1])
$p2 = $this->len[$i1] - 1;
}
/*
実行
*/
$sw = 0;
while ($sw == 0) {
$lid = $this->ind[$i1][$p1];
$this->ind[$i1][$p1] = $this->ind[$i1][$p2];
$this->ind[$i1][$p2] = $lid;
$p1++;
$p2--;
if ($p1 >= $p2)
$sw = 1;
}
}
}
}
/**********************************************************************/
/* 突然変異（スクランブル．２点間の遺伝子順序をランダムに並べ替える） */
/* pr : 突然変異率 */
/* wd : >0 : 幅を固定 */
/* =0 : 幅をランダム(default) */
/**********************************************************************/
function M_scram($pr, $wd = 0)
{
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1 && uniform() <= $pr) {
/*
区間の決定
*/
if ($wd == 0) {
$p1 = intval(uniform() * $this->len[$i1]);
if ($p1 >= $this->len[$i1])
$p1 = $this->len[$i1] - 1;
$sw = 0;
while ($sw == 0) {
$p2 = intval(uniform() * $this->len[$i1]);
if ($p2 >= $this->len[$i1])
$p2 = $this->len[$i1] - 1;
if ($p2 != $p1)
$sw = 1;
}
if ($p1 > $p2) {
$p = $p1;
$p1 = $p2;
$p2 = $p;
}
}
else {
$p1 = $this->len[$i1];
while ($p1 > $this->len[$i1]-2)
$p1 = intval(uniform() * $this->len[$i1]);
$p2 = $p1 + $wd - 1;
if ($p2 >= $this->len[$i1])
$p2 = $this->len[$i1] - 1;
}
/*
実行
*/
for ($i2 = $p1; $i2 <= $p2; $i2++) {
$p = intval(uniform() * ($p2 - $p1 + 1) + $p1);
if ($p > $p2)
$p = $p2;
$ld = $this->ind[$i1][$i2];
$this->ind[$i1][$i2] = $this->ind[$i1][$p];
$this->ind[$i1][$p] = $ld;
}
}
}
}
/**********************************************************************/
/* 突然変異（転座．２点間の遺伝子を他の位置のものと置き換える．ただし */
/* 重複部分はそのままとする） */
/* pr : 突然変異率 */
/* wd : >0 : 幅を固定 */
/* =0 : 幅をランダム(default) */
/**********************************************************************/
function M_chg($pr, $wd = 0)
{
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1 && uniform() <= $pr) {
/*
区間等の決定（[p1,p2]と[p3,p4]の入れ替え）
*/
// p1
$p1 = intval(uniform() * $this->len[$i1]);
if ($p1 >= $this->len[$i1])
$p1 = $this->len[$i1] - 1;
// p3
$sw = 0;
while ($sw == 0) {
$p3 = intval(uniform() * $this->len[$i1]);
if ($p3 >= $this->len[$i1])
$p3 = $this->len[$i1] - 1;
if ($p3 != $p1)
$sw = 1;
}
// 小さい方をp1,p2にする
if ($p1 > $p3) {
$p = $p1;
$p1 = $p3;
$p3 = $p;
}
// p4, p2
$p4 = ($wd == 0) ? intval(uniform() * ($this->len[$i1] - $p3)) + $p3 : $p1 + $wd - 1;
if ($p4 >= $this->len[$i1])
$p4 = $this->len[$i1] - 1;
$p2 = $p1 + ($p4 - $p3);
// 重複部分のチェック
if ($p2 >= $p3) {
$p = $p3 - 1;
$p3 = $p2 + 1;
$p2 = $p;
$p4 = $p3 + ($p2 - $p1);
}
/*
実行
*/
$p = $p3;
for ($i2 = $p1; $i2 <= $p2; $i2++) {
$ld = $this->ind[$i1][$i2];
$this->ind[$i1][$i2] = $this->ind[$i1][$p];
$this->ind[$i1][$p] = $ld;
$p++;
}
}
}
}
/**********************************************************************/
/* 突然変異（重複．２点間の遺伝子を他の位置にコピーする */
/* pr : 突然変異率 */
/* wd : >0 : 幅を固定 */
/* =0 : 幅をランダム(deafult) */
/**********************************************************************/
function M_dup($pr, $wd = 0)
{
/*
データのチェック
*/
if ($this->dup_a == 0)
exit("***error 突然変異方法が不適当 (M_dup)\n");
/*
実行
*/
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1 && uniform() <= $pr) {
// 区間の決定（[p1,p2]を[p3,p4]にコピー）
// p1
$p1 = intval(uniform() * $this->len[$i1]);
if ($p1 >= $this->len[$i1])
$p1 = $this->len[$i1] - 1;
// p3
$sw = 0;
while ($sw == 0) {
$p3 = intval(uniform() * $this->len[$i1]);
if ($p3 >= $this->len[$i1])
$p3 = $this->len[$i1] - 1;
if ($p3 != $p1)
$sw = 1;
}
// 区間を決める
if ($p3 > $p1) {
$p4 = ($wd == 0) ? intval(uniform() * ($this->len[$i1] - $p3)) + $p3 : $p3 + $wd - 1;
if ($p4 >= $this->len[$i1])
$p4 = $this->len[$i1] - 1;
$p2 = $p1 + ($p4 - $p3);
}
else {
$p2 = ($wd == 0) ? intval(uniform() * ($this->len[$i1] - $p1)) + $p1 :$p1 + $wd - 1;
if ($p2 >= $this->len[$i1])
$p2 = $this->len[$i1] - 1;
$p4 = $p3 + ($p2 - $p1);
}
// 実行
$p = $p4;
for ($i2 = $p2; $i2 >= $p1; $i2--) {
$this->ind[$i1][$p] = $this->ind[$i1][$i2];
$p--;
}
}
}
}
/******************************************************/
/* 突然変異（摂動．値をある量だけ変化させる） */
/* pr : 突然変異率 */
/* method : =0 : 正規分布(default) */
/* =1 : 一様分布 */
/* m : 平均または一様分布の下限(default=0.0) */
/* s : 標準偏差または一様分布の上限(default=1.0) */
/******************************************************/
function M_per($pr, $method = 0, $m = 0.0, $s = 1.0)
{
$wd = 0.0;
/*
データのチェックと初期設定
*/
if ($this->dup_a == 0)
exit("***error 突然変異方法が不適当 (M_per)\n");
if ($method > 0)
$wd = $s - $m;
/*
実行
*/
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1) {
for ($i2 = 0; $i2 < $this->len[$i1]; $i2++) {
if (uniform() <= $pr) {
if ($method == 0)
$w = norm_d($m, $s);
else {
$w = uniform() * $wd;
if (uniform() < 0.5)
$w = -$w;
}
$x1 = (double)$this->ind[$i1][$i2] + $w;
if ($x1 > $this->allele_u)
$x1 = $this->allele_u;
else {
if ($x1 < $this->allele_l)
$x1 = $this->allele_l;
}
$this->ind[$i1][$i2] = intval($x1);
}
}
}
}
}
/**********************************************************************/
/* 突然変異（挿入．ある長さの遺伝子を挿入する） */
/* pr : 突然変異率 */
/* wd : >0 : 幅を固定 */
/* =0 : 幅をランダム(default) */
/**********************************************************************/
function M_ins($pr, $wd = 0)
{
/*
データのチェック
*/
if ($this->dup_a == 0 || $this->min_len < 0)
exit("***error 突然変異方法が不適当 (M_ins)\n");
/*
実行
*/
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1 && uniform() <= $pr) {
// 挿入位置の決定
$p = intval(uniform() * ($this->len[$i1]+1));
if ($p > $this->len[$i1])
$p = $this->len[$i1];
// 挿入する遺伝子長の決定
$l = ($wd == 0) ? intval(uniform() * ($this->max_len - $this->len[$i1] + 1)) : $wd;
if ($l > $this->max_len-$this->len[$i1])
$l = $this->max_len - $this->len[$i1];
else {
if ($l <= 0)
$l = 1;
}
// 実行
// 挿入場所の確保
if ($p < $this->len[$i1]) {
for ($i2 = $this->len[$i1]+$l-1; $i2 >= $p; $i2--)
$this->ind[$i1][$i2] = $this->ind[$i1][$i2-$l];
}
// 挿入場所の遺伝子の決定
for ($i2 = $p; $i2 < $p+$l; $i2++) {
$ld = intval(uniform() * ($this->allele_u - $this->allele_l + 1) + $this->allele_l);
if ($ld > $this->allele_u)
$ld = $this->allele_u;
$this->ind[$i1][$i2] = $ld;
}
$this->len[$i1] += $l;
}
}
}
/**********************************************************************/
/* 突然変異（削除．ある長さの遺伝子を削除する） */
/* pr : 突然変異率 */
/* wd : >0 : 幅を固定 */
/* =0 : 幅をランダム(default) */
/**********************************************************************/
function M_del($pr, $wd = 0)
{
/*
データのチェック
*/
if ($this->dup_a == 0 || $this->min_len < 0)
exit("***error 突然変異方法が不適当 (M_del)\n");
exit(1);
/*
実行
*/
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1 && uniform() <= $pr) {
// 削除位置の決定
$p = intval(uniform() * $this->len[$i1]);
if ($p >= $this->len[$i1])
$p = $this->len[$i1] - 1;
// 削除する遺伝子長の決定
$max = ($this->len[$i1]-$this->min_len < $this->len[$i1]-$p) ? $this->len[$i1] - $this->min_len : $this->len[$i1] - $p;
$l = ($wd == 0) ? intval(uniform() * $max + 1) : $wd;
if ($l > $max)
$l = $max;
// 実行
for ($i2 = 0; $i2 < $this->len[$i1]-$p-$l; $i2++)
$this->ind[$i1][$p+$i2] = $this->ind[$i1][$p+$i2+$l];
$this->len[$i1] -= $l;
}
}
}
/*********************************************************************/
/* 淘汰（エリート・ルーレット選択） */
/* elite : エリートで残す個体数(default=0) */
/* s_method : ルーレット板の作成方法(default=1) */
/* =0 : 適応度をそのまま使用 */
/* =1 : 最小値からの差（ただし，α以下の場合はα） */
/* =2 : 評価値に順位をつけ，減少率βで線形化 */
/* s_bias : α，または，method=2の場合は初期値(default=0) */
/* s_step : β(default=1) */
/*********************************************************************/
function S_roul($elite = 0, $s_method = 1, $s_bias = 0.0, $s_step = 1.0)
{
$count = 0;
$k = 0;
$n = 0;
/*
値のチェックと初期設定
*/
if ($s_method != 0 && $s_method != 2)
$s_method = 1;
if ($elite > $this->size)
exit("***error エリートで残す数が多すぎる (S_roul)\n");
if ($s_method == 2 && $s_step <= 0.0)
$s_step = 1.0;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++)
$this->s_w[$i1] = 0;
/*
重複個体を削除
*/
if ($this->dup_s == 0) {
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 0) {
for ($i2 = $i1+1; $i2 < $this->size+$this->max_ch; $i2++) {
if ($this->pi_w[$i2] > 0 && $this->len[$i1] == $this->len[$i2]) {
$sw = 0;
for ($i3 = 0; $i3 < $this->len[$i1] && $sw == 0; $i3++) {
if ($this->ind[$i1][$i3] != $this->ind[$i2][$i3])
$sw = 1;
}
if ($sw == 0)
$this->pi_w[$i2] = 0;
}
}
}
}
}
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1)
$n++;
}
if ($n < 0 || $this->dup_s == 0 && $n < $this->size)
exit("***error 残す個体がない (S_roul)\n");
/*
淘汰して残す個体を選ぶ
*/
// エリートの選択
$sw = 0;
while ($k < $elite && $k < $n && $sw == 0) {
$max = -1;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] > 1 && $this->s_w[$i1] == 0) {
if ($max < 0 || $this->pi[$i1] > $this->pi[$max])
$max = $i1;
}
}
if ($max < 0)
$sw = 1;
else {
$this->s_w[$max] = 1;
$k++;
}
}
// ルーレット選択
while ($count < $this->size+$this->max_ch && $k < $this->size) {
$p = $this->Select($s_method, $s_bias, $s_step);
if ($this->dup_s == 0 && $this->s_w[$p] > 0)
$count++;
else {
$count = 0;
$this->s_w[$p]++;
$k++;
}
}
// 選択に失敗した場合の処理
if ($this->dup_s == 0 && $k < $this->size) {
for ($i1 = 0; $i1 < $this->size+$this->max_ch && $k < $this->size; $i1++) {
if ($this->pi_w[$i1] > 1 && $this->s_w[$i1] == 0) {
$this->s_w[$i1] = 1;
$k++;
}
}
}
// 複数回選択されたものの処理
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->s_w[$i1] == 0)
$this->pi_w[$i1] = 0;
}
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->s_w[$i1] > 0) {
if ($this->s_w[$i1] > 1) {
for ($i2 = 2; $i2 <= $this->s_w[$i1]; $i2++) {
$k = $this->Position(-1);
$this->len[$k] = $this->len[$i1];
$this->pi_w[$k] = 2;
$this->pi[$k] = $this->pi[$i1];
for ($i3 = 0; $i3 < $this->len[$i1]; $i3++)
$this->ind[$k][$i3] = $this->ind[$i1][$i3];
}
}
}
}
}
}
/***********************************/
/* [0, 1] 区間の一様分布変量の発生 */
/***********************************/
function uniform()
{
return mt_rand() / mt_getrandmax();
}
/***********************************/
/* 正規分布変量の発生 */
/* m : 平均 */
/* s : 標準偏差 */
/* return : 正規分布変量 */
/***********************************/
function norm_d($m, $s)
{
$x = 0.0;
for ($i1 = 0; $i1 < 12; $i1++)
$x += uniform();
$x = $s * ($x - 6.0) + $m;
return $x;
}
/*******************/
/* クラスTSPの定義 */
/*******************/
class TSP extends Species {
private $max_gen; // 最大世代交代数
private $kosa_m; // 交叉方法
// =-1 : 交叉を使用しない
// =0 : 親のコピー
// =1 : 循環交叉
// =2 : 部分的交叉
// =3 : 順序交叉
// =4 : 一様順序交叉
// =5 : 一様位置交叉
// =6 : エッジ組み替え交叉
// =7 : サブツアー交叉
private $kosa; // 交叉確率
private $k_point; // 交差点の数（負の時は，1から-k_point間のランダム）
private $k_vr; // =0 : 両親とも同じ位置で交叉
// =1 : 両親が異なる位置で交叉（遺伝子長は可変）
private $k_method; // 交叉の時の親の選択方法
// =-1 : ランダム
// =0 : 適応度をそのまま使用
// =1 : 最小値からの差（ただし，α以下の場合はα）
// =2 : 評価値に順位をつけ，減少率βで線形化
private $k_bias; // α，または，method=2の場合は初期値
private $k_step; // β
private $mute_m; // 突然変異方法
// =-1 : 突然変異を使用しない
// =0 : 移動
// =1 : 逆位
// =2 : スクランブル
// =3 : 転座
private $mute; // 突然変異率
private $wd; // 突然変異に使用する部分遺伝子長
private $m_mean; // 摂動の平均値
private $m_std; // 摂動の標準偏差
private $elite; // エリート選択で残す数
private $s_method; // ルーレット板の作成方法
// =0 : 適応度をそのまま使用
// =1 : 最小値からの差（ただし，α以下の場合はα）
// =2 : 評価値に順位をつけ，減少率βで線形化
private $s_bias; // α，または，s_method=2の場合は初期値
private $s_step; // β
private $out_d; // 表示間隔
private $out_lvl; // 出力レベル
// =0 : 最終出力だけ
// n>0 : ｎ世代毎に出力（負の時はファイル）
private $out_m; // 出力方法
// =0 : すべてを出力
// =1 : 最大適応度の個体だけを出力
private $o_file; // 出力ファイル名
private $city; //都市の位置データ
private $n_city; // 都市の数
private $rg; // 都市間の距離
private $kinbo; // 近傍探索（０：行わない，１：行う）
private $neib; // 近傍（2 or 3）
private $sel; // エッジの選択方法
// =0 : 最良のものを選択
// =1 : 最初のものを選択
/***************************************/
/* コンストラクタ */
/* name1 : Species定義ファイル名 */
/* name2 : TSP定義ファイル名 */
/* seed : 乱数の初期値 */
/***************************************/
function TSP ($name1, $name2, $seed)
{
parent::Species($name1, $seed);
// 基本データの入力
$in = fopen($name2, "r");
fscanf($in, "%*s %d %*s %d", $this->out_lvl, $this->out_m);
fscanf($in, "%*s %s %*s %d", $this->o_file, $this->out_d);
fscanf($in, "%*s %d %*s %lf %*s %d %*s %d %*s %d %*s %lf %*s %lf", $this->kosa_m, $this->kosa, $this->k_point, $this->k_vr, $this->k_method, $this->k_bias, $this->k_step);
fscanf($in, "%*s %d %*s %lf %*s %d %*s %lf %*s %lf", $this->mute_m, $this->mute, $this->wd, $this->m_mean, $this->m_stds);
fscanf($in, "%*s %d %*s %d %*s %lf %*s %lf", $this->elite, $this->s_method, $this->s_bias, $this->s_step);
fscanf($in, "%*s %d %*s %d", $this->n_city, $this->max_gen);
fscanf($in, "%*s %d %*s %d", $this->kinbo, $this->neib);
fscanf($in, "%*s %d", $this->sel);
if ($this->kinbo > 0 && $this->neib != 2 && $this->neib != 3)
exit("***error 近傍の値が不適当 \n");
if ($this->n_city != $this->max_len)
exit("***error 都市数が不適当 \n");
// 都市の位置データ
$this->city = array($this->n_city);
for ($i1 = 0; $i1 < $this->n_city; $i1++) {
$this->city[$i1] = array(2);
fscanf($in, "%d %d", $this->city[$i1][0], $this->city[$i1][1]);
}
// 距離テーブル
$this->rg = array($this->n_city);
for ($i1 = 0; $i1 < $this->n_city; $i1++) {
$this->rg[$i1] = array($this->n_city);
for ($i2 = $i1+1; $i2 < $this->n_city; $i2++) {
$x = $this->city[$i2][0] - $this->city[$i1][0];
$y = $this->city[$i2][1] - $this->city[$i1][1];
$this->rg[$i1][$i2] = round(sqrt($x * $x + $y * $y));
}
}
for ($i1 = 1; $i1 < $this->n_city; $i1++) {
for ($i2 = 0; $i2 < $i1; $i2++)
$this->rg[$i1][$i2] = $this->rg[$i2][$i1];
}
fclose($in);
}
/**************/
/* 全体の制御 */
/**************/
function Control()
{
$gen = 1;
// 初期集団の発生
$this->Init_std();
// 評価
if ($this->kinbo > 0)
$this->Kinbo();
else
$this->Adap();
// 出力
printf("***世代 %d 適応度 max %f (%d) mean %f\n", $gen, $this->max, $this->max_n, $this->mean);
if (abs($this->out_lvl) > 0)
$this->Output($gen);
// 世代交代
for ($gen = 2; $gen <= $this->max_gen; $gen++) {
// 交叉
switch ($this->kosa_m) {
case -1:
break;
case 0:
$this->C_copy(); // 親のコピー
break;
case 1:
$this->C_cycle($this->kosa); // 循環交叉
break;
case 2:
$this->C_part($this->kosa); // 部分的交叉
break;
case 3:
$this->C_seq($this->kosa); // 順序交叉
break;
case 4:
$this->C_useq($this->kosa); // 一様順序交叉
break;
case 5:
$this->C_upos($this->kosa); // 一様位置交叉
break;
case 6:
$this->C_edge($this->kosa); // エッジ組み替え交叉
break;
case 7:
$this->C_sub($this->kosa, $this->k_point); // サブツアー交叉
break;
default:
break;
}
// 突然変異
switch ($this->mute_m) {
case -1:
break;
case 0:
$this->M_move($this->mute); // 移動
break;
case 1:
$this->M_inv($this->mute); // 逆位
break;
case 2:
$this->M_scram($this->mute); // スクランブル
break;
case 3:
$this->M_chg($this->mute); // 転座
break;
default:
break;
}
// 適応度
if ($this->kinbo > 0)
$this->Kinbo();
else
$this->Adap();
// 淘汰
$this->S_roul($this->elite);
// 出力
if ($gen%$this->out_d == 0)
printf("***世代 %d 適応度 max %f (%d) mean %f\n", $gen, $this->max, $this->max_n, $this->mean);
if (abs($this->out_lvl) > 0) {
if ($gen%abs($this->out_lvl) == 0)
$this->Output($gen);
}
}
$gen--;
$k1 = $this->out_m;
$this->out_m = 0;
printf("***世代 %d 適応度 max %f (%d) mean %f\n", $gen, $this->max, $this->max_n, $this->mean);
$this->Output($gen);
$this->out_m = $k1;
}
/*********************************/
/* 距離の計算 */
/* n_c : 都市の数 */
/* p : 都市番号 */
/* return : 距離（負） */
/*********************************/
function Kyori($n_c, $p)
{
$range = 0;
$n1 = $p[0];
for ($i1 = 1; $i1 < $n_c; $i1++) {
$n2 = $p[$i1];
$range -= $this->rg[$n1][$n2];
$n1 = $n2;
}
$n2 = $p[0];
$range -= $this->rg[$n1][$n2];
return $range;
}
/****************/
/* 適応度の計算 */
/****************/
function Adap()
{
$k = 0;
$this->mean = 0.0;
$this->max = 0.0;
$this->max_n = -1;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1) {
$this->pi_w[$i1] = 2;
$this->pi[$i1] = $this->Kyori($this->len[$i1], $this->ind[$i1]);
}
if ($this->pi_w[$i1] > 0) {
$k++;
$this->mean += $this->pi[$i1];
if ($this->max_n < 0 || $this->pi[$i1] > $this->max) {
$this->max = $this->pi[$i1];
$this->max_n = $i1;
}
}
}
if ($k > 0)
$this->mean /= $k;
}
/**************************************/
/* エッジの入れ替え */
/* n_city : 都市の数 */
/* seq : 訪問する順番 */
/* r_m : 距離の負値 */
/* return : =0 : 改善がなかった */
/* =1 : 改善があった */
/**************************************/
function Change($n_city, &$seq, &$r_m)
{
$ch = 0;
$sw = 0;
$max = $r_m;
$n3 = intval(uniform() * ($n_city - 2));
if ($n3 > $n_city-3)
$n3 = $n_city - 3;
// ２近傍
for ($i1 = 0; $i1 <= $n_city-3 && $ch == 0; $i1++) {
if ($n3 == 0)
$n1 = $n_city - 2;
else
$n1 = $n_city - 1;
for ($i2 = $n3+2; $i2 <= $n1 && $ch == 0; $i2++) {
// 枝の場所（(n3,n3+1), (k1,k2)）
$k1 = $i2;
if ($i2 == $n_city-1)
$k2 = 0;
else
$k2 = $i2 + 1;
// 枝の入れ替え
$this->kou1[0] = $seq[$n3];
$k = 1;
for ($i3 = $k1; $i3 >= $n3+1; $i3--) {
$this->kou1[$k] = $seq[$i3];
$k++;
}
$nn = $k2;
while ($nn != $n3) {
$this->kou1[$k] = $seq[$nn];
$k++;
$nn++;
if ($nn > $n_city-1)
$nn = 0;
}
// 評価
$r = $this->Kyori($n_city, $this->kou1);
if ($r > $max) {
$max = $r;
$sw = 1;
for ($i3 = 0; $i3 < $n_city; $i3++)
$this->kou2[$i3] = $this->kou1[$i3];
if ($this->sel > 0)
$ch = 1;
}
}
$n3++;
if ($n3 > $n_city-3)
$n3 = 0;
}
// ３近傍
if ($this->neib == 3 && $ch == 0) {
for ($i1 = 0; $i1 <= $n_city-3 && $ch == 0; $i1++) {
$n1 = $n_city - 2;
$n2 = $n_city - 1;
for ($i2 = $n3+1; $i2 <= $n1 && $ch == 0; $i2++) {
for ($i3 = $i2+1; $i3 <= $n2 && $ch == 0; $i3++) {
// 枝の場所（(n3,n3+1), ($i2,$i2+1), (k1,k2)）
$k1 = $i3;
if ($i3 == $n_city-1)
$k2 = 0;
else
$k2 = $i3 + 1;
// 枝の入れ替えと評価
// 入れ替え（その１）
$this->kou1[0] = $seq[$n3];
$k = 1;
for ($i4 = $i2; $i4 >= $n3+1; $i4--) {
$this->kou1[$k] = $seq[$i4];
$k++;
}
for ($i4 = $k1; $i4 >= $i2+1; $i4--) {
$this->kou1[$k] = $seq[$i4];
$k++;
}
$nn = $k2;
while ($nn != $n3) {
$this->kou1[$k] = $seq[$nn];
$k++;
$nn++;
if ($nn > $n_city-1)
$nn = 0;
}
// 評価（その１）
$r = $this->Kyori($n_city, $this->kou1);
if ($r > $max) {
$max = $r;
$sw = 1;
for ($i3 = 0; $i3 < $n_city; $i3++)
$this->kou2[$i3] = $this->kou1[$i3];
if ($this->sel > 0)
$ch = 1;
}
// 入れ替え（その２）
$this->kou1[0] = $seq[$n3];
$k = 1;
for ($i4 = $k1; $i4 >= $i2+1; $i4--) {
$this->kou1[$k] = $seq[$i4];
$k++;
}
for ($i4 = $n3+1; $i4 <= $i2; $i4++) {
$this->kou1[$k] = $seq[$i4];
$k++;
}
$nn = $k2;
while ($nn != $n3) {
$this->kou1[$k] = $seq[$nn];
$k++;
$nn++;
if ($nn > $n_city-1)
$nn = 0;
}
// 評価（その２）
$r = $this->Kyori($n_city, $this->kou1);
if ($r > $max) {
$max = $r;
$sw = 1;
for ($i3 = 0; $i3 < $n_city; $i3++)
$this->kou2[$i3] = $this->kou1[$i3];
if ($this->sel > 0)
$ch = 1;
}
// 入れ替え（その３）
$this->kou1[0] = $seq[$n3];
$k = 1;
for ($i4 = $i2+1; $i4 <= $k1; $i4++) {
$this->kou1[$k] = $seq[$i4];
$k++;
}
for ($i4 = $i2; $i4 >= $n3+1; $i4--) {
$this->kou1[$k] = $seq[$i4];
$k++;
}
$nn = $k2;
while ($nn != $n3) {
$this->kou1[$k] = $seq[$nn];
$k++;
$nn++;
if ($nn > $n_city-1)
$nn = 0;
}
// 評価（その３）
$r = $this->Kyori($n_city, $this->kou1);
if ($r > $max) {
$max = $r;
$sw = 1;
for ($i3 = 0; $i3 < $n_city; $i3++)
$this->kou2[$i3] = $this->kou1[$i3];
if ($this->sel > 0)
$ch = 1;
}
// 入れ替え（その４）
$this->kou1[0] = $seq[$n3];
$k = 1;
for ($i4 = $i2+1; $i4 <= $k1; $i4++) {
$this->kou1[$k] = $seq[$i4];
$k++;
}
for ($i4 = $n3+1; $i4 <= $i2; $i4++) {
$this->kou1[$k] = $seq[$i4];
$k++;
}
$nn = $k2;
while ($nn != $n3) {
$this->kou1[$k] = $seq[$nn];
$k++;
$nn++;
if ($nn > $n_city-1)
$nn = 0;
}
// 評価（その４）
$r = $this->Kyori($n_city, $this->kou1);
if ($r > $max) {
$max = $r;
$sw = 1;
for ($i3 = 0; $i3 < $n_city; $i3++)
$this->kou2[$i3] = $this->kou1[$i3];
if ($this->sel > 0)
$ch = 1;
}
}
}
$n3++;
if ($n3 > $n_city-3)
$n3 = 0;
}
}
// 設定
if ($sw > 0) {
$r_m = $max;
for ($i1 = 0; $i1 < $n_city; $i1++)
$seq[$i1] = $this->kou2[$i1];
}
return $sw;
}
/**************/
/* 近傍の探索 */
/**************/
function Kinbo()
{
$k = 0;
$this->max = 0.0;
$this->max_n = -1;
$this->mean = 0.0;
for ($i1 = 0; $i1 < $this->size+$this->max_ch; $i1++) {
if ($this->pi_w[$i1] == 1) {
$this->pi_w[$i1] = 2;
$sw = 1;
$r = $this->Kyori($this->len[$i1], $this->ind[$i1]);
while ($sw > 0)
$sw = $this->Change($this->len[$i1], $this->ind[$i1], $r);
$this->pi[$i1] = $r;
}
if ($this->pi_w[$i1] > 0) {
$k++;
$this->mean += $this->pi[$i1];
if ($this->max_n < 0 || $this->pi[$i1] > $this->max) {
$this->max = $this->pi[$i1];
$this->max_n = $i1;
}
}
}
if ($k > 0)
$this->mean /= $k;
}
/*****************************/
/* 結果の出力 */
/* gen : 現在の世代番号 */
/*****************************/
function Output($gen)
{
$k = 0;
if ($this->out_lvl >= 0) {
printf(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ ");
fscanf(STDIN, "%d", $pr);
}
else
$pr = -1;
if ($pr != 0) {
// 出力先の決定と評価値の出力
if ($pr > 0) {
$out = STDOUT;
fgets(STDIN);
}
else {
$x = getdate();
$now = $x["hours"]."時".$x["minutes"]."分".$x["seconds"]."秒";
$out = fopen($this->o_file, "ab");
fwrite($out, "***世代 ".$gen." 適応度 max ".$this->max." (".$this->max_n.") mean ".$this->mean." 時間 ".$now."\n");
}
// 巡回順序の出力
if ($this->out_m == 0) {
for ($i1 = 0; $i1 < $this->len[$this->max_n]; $i1++) {
$n = $this->ind[$this->max_n][$i1];
fwrite($out, $n." ".$this->city[$n][0]." ".$this->city[$n][1]."\n");
if ($pr > 0) {
$k++;
if ($k == $pr) {
fgets(STDIN);
$k = 0;
}
}
}
}
if ($pr < 0)
fclose($out);
}
}
}
/****************/
/* main program */
/****************/
// 入力ミス
if (count($argv) <= 1)
exit("***error ファイル名を入力して下さい\n");
// 入力ＯＫ
else {
// ファイルのオープン
$in = fopen($argv[1], "rb");
if ($in == NULL)
exit("***error ファイル名が不適当です\n");
// 入力データファイル名の入力
fscanf($in, "%d", $n); // データの数
$seed = array($n);
$i_file1 = array($n);
$i_file2 = array($n);
for ($i1 = 0; $i1 < $n; $i1++) {
$seed[$i1] = 1000 * $i1 + 1234567;
fscanf($in, "%s %s", $i_file1[$i1], $i_file2[$i1]);
}
fclose($in);
// 実行（乱数の初期値を変える）
for ($i1 = 0; $i1 < $n; $i1++) {
printf("\n+++++ケース %d+++++\n", $i1+1);
$tsp = new TSP($i_file1[$i1], $i_file2[$i1], $seed[$i1]);
$tsp->Control();
}
}
//----------------ケーススタディデータ(data_ct.txt)------
/*
3
data1_t.txt data2_t.txt
data1_t.txt data2_t.txt
data1_t.txt data2_t.txt
*/
//---------------Species記述データ(data1_t.txt)---------
/*
対立遺伝子上限 9 対立遺伝子下限 0
最大遺伝子長 10 最小遺伝子長（負の時は，最大遺伝子長で固定） -1
遺伝子の重複 0 個体の重複（同じ染色体の個体） 0
集団サイズ 10 子供 10
*/
//---------------TSP記述データ(data2_t.txt)--------
/*
出力レベル(負はファイル) 10 出力方法(0:適応度＋順番，1:適応度) 0
出力ファイル名 out1.txt 表示間隔 10
交叉方法 1 交叉確率 1.0 点 5 位置 0 方法 1 バイアス 0 ステップ 1
突然変異方法 1 突然変異率 0.03 幅 1 平均 0.0 標準偏差 1.0
エリート 2 方法 1 バイアス 0 ステップ 1
都市数 10 最大世代交代数 2000
近傍探索(0:行わない，1:行う) 0 近傍（2or3） 2
選択方法(0:最良，1:最初) 1
-58 37
55 -19
6 -79
27 -30
44 -94
33 -58
-94 87
-9 3
33 69
43 -57
*/
?>