Ｓｋｙテックブログ（技術ブログ）

記事検索

検索ワードを入力してください。
Sky Tech Blog
遺伝的アルゴリズムの​活用法
技術情報2024.10.01

遺伝的アルゴリズムの​活用法

遺伝的アルゴリズム（GA）は、1975年にジョン・H・ホランドが提案した近似解を探索するアルゴリズムです。解を遺伝子で表現し、強い個体が生き残り、弱い個体は淘汰される世代交代を繰り返して最適解を探索します。トラックの配送問題など、複雑な組合せ問題に適用可能です。

アルゴリズムには様々な種類がありますが、機械学習の一つである進化の仕組みを利用した遺伝的アルゴリズムをご紹介いたします。

遺伝的アルゴリズムは、英語表記genetic algorithm、略称GAと呼ばれ、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するアルゴリズムです。

アルゴリズムの流れは以下となります。
名前の通り、解を遺伝子で表現した個体を作成し、強い個体が生き残り、弱い個体は淘汰されるように世代交代を繰り返して最適解を探索します。

理屈はわかっても処理の流れだけでは実装イメージが付きにくい為、以下例題でご説明いたします。
トラック４台で２０地点を配送する為、組合せは４の２０乗の 1,099,511,627,776 通りとなり、積載量の多いトラックは拠点から遠い地点を担当するなど条件を決めて解を導き出すことは可能ですが、遺伝的アルゴリズムを利用すれば容易に最適解を出すことが可能です。

【例題】

以下図中央の拠点からトラック４台で２０地点（●の地点）に荷物を配送します。トラックによって積載量が異なり、それぞれの積載可能数は以下となります。
全ての荷物を配送し終え全トラックが拠点に戻ってくるまでが最短時間となる組合せを求めましょう。

それでは、各処理の詳細を説明いたします。
まずは個体の作成ですが、各地点をどのトラックが担当するかを以下のように配列で表現します。これが遺伝子情報となります。

次に、適応度評価として各個体の点数付けをします。点数積み上げや特定条件で減点するなど評価の仕方はどんなものでも構いませんが、ここで点数が高い個体が次世代に生き残る事になるので適応度は非常に重要です。
今回は、各トラックの担当地点を地点間の距離が最短になるように並べなおした上で距離を算出し、最大距離となったトラックの移動距離をそのまま適応度とします。

続いて、個体の選択・交叉・突然変異です。
現世代として一定数作成した個体の中から個体を選択しますが、優良個体（適応度の高い個体）が選択される確率が高まるようにします。

ルーレット選択やトーナメント選択、ランキング選択といった方式がありますが、同じ個体ばかり選択されると交叉した時の遺伝子情報が似通ってしまう為、確率で選択することが重要です。今回はルーレット選択を採用します。
なお、全て確率に任せると、せっかく作成された優良個体が淘汰される可能性がある為、エリートを次世代に残す場合があります。これをエリート選択と言います。

選択ができたら次は交叉です。
交叉にはランダムに選んだ位置以降を入れ替える一点交叉、二点交叉など様々な方式があります。遺伝子の内容によって交叉の方式は変わる為、どれが良いということはありません。今回は各要素を二分の一の確率で入れ替える一様交叉と呼ばれる方式を利用します。

次は突然変異です。
上述の交叉の繰り返しだけでは似た遺伝子情報ばかりとなり特定範囲しか検索されません。これを避ける為にランダムで遺伝子の一部を書き換える方法を取ります。
但し、突然変異を多く発生させるとただのランダムな探索になる為、突然変異の発生率は１～２％程に抑えるのが良いとされています。

後はこれらを繰り返し最良個体を求めるだけです。
視覚的に解りやすいように遺伝子を半分に区切りそれぞれの総和をX軸、Y軸とした分散イメージと最適解を描画いたしました。分散イメージは世代交代を繰り返し最適解に収束していく動きが解り易いのでは無いかと思います。
最適解に関しても、経路は適応度算出を変える事でもう少し改善できそうですが、トラック４台で分散されており概ね問題ないように思われます。

完全な実装サンプルは以下となります。JavaScriptで記述しておりますので各ブラウザで動作いたします。

index.html

<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UYF-8" />
<script src="ga.js"></script>
<script src="visualize.js"></script>
<title>GA</title>
</head>
<body>
    <div style="display:flex;">
        <div style="padding: 5px;">
            <div>■Environment Setting<br /></div>
            <div style="display:table;">
                <div>
                    <div style="display:table-cell; width: 200px;">POI COUNT: </div>
                    <div style="display:table-cell;"><input style="text-align: right;" type="text" id="poiCount" value="20"> ※地点数</div>
                </div>
                <div>
                    <div style="display:table-cell; width: 200px;">POPULATION COUNT: </div>
                    <div style="display:table-cell;"><input style="text-align: right;" type="text" id="populationCount" value="1000"> ※世代あたりの個体数</div>
                </div>
                <div>
                    <div style="display:table-cell; width: 200px;">MUTATE RATE: </div>
                    <div style="display:table-cell;"><input style="text-align: right;" type="text" id="mutateRate" value="0.02"> ※突然変異率</div>
                </div>
                <div>
                    <div style="display:table-cell; width: 200px;">MUTATE GENE RATE: </div>
                    <div style="display:table-cell;"><input style="text-align: right;" type="text" id="mutateGeneRate" value="0.1"> ※突然変異時の遺伝子組み換え率</div>
                </div>
            </div>
            <div>
                <input type="button" id="init" value="Init" onclick="init()">
                <input type="button" id="start" value="Start" onclick="start()">
                <input type="button" id="stop" value="Stop" onclick="stop()">
                <br />
                <br />
            </div>
            <div style="padding: 5px;">
                <div>■POI Info<br /></div>  
                <div style="width: 600px;" id="environmentInfoText"></div>
                <br />
                <div>■Top Candidate<br /></div>
                <div style="width: 600px;" id="generationInfoText"></div>
            </div>
        </div>
        <div>
            <div><canvas width="100" height="100" id="scatterPlotCanvas" style="background-color:white; outline: black 2px solid;"></canvas></div>
            <div><canvas width="100" height="100" id="optSolutionCanvas" style="background-color:white; outline: black 2px solid;"></canvas></div>
            <div id="resultText"></div>
        </div>
    </div>
</body>
</html>

ga.js

class Environment {
	constructor(poiCount, populationCount, mutateRate, mutateGeneRate) {
		this.populationCount = populationCount;
		this.mutateRate = mutateRate;
		this.mutateGeneRate = mutateGeneRate;
		this.center = { "x": poiCount / 2, "y": poiCount / 2 }; // 拠点
		this.truck = [ 
			{ "id": "A", "capacity": 5, "color": "rgba(255 0 0 / 70%)" }, 
			{ "id": "B", "capacity": 4, "color": "rgba(0 255 0 / 70%)" }, 
			{ "id": "C", "capacity": 3, "color": "rgba(0 0 255 / 70%)" }, 
			{ "id": "D", "capacity": 2, "color": "rgba(200 200 0 / 70%)" }
		];
		this.poi = [];
		while (this.poi.length < poiCount) {
			let x = Math.floor(Math.random() * poiCount);
			let y = Math.floor(Math.random() * poiCount);
			// 拠点及び重複地点は除外
			if (!(this.center.x == x && this.center.y == y) && !this.poi.find((p) => p.x == x && p.y == y)) {
				this.poi.push({ "x": x, "y": y });
			}
		}
		this.worstDistance = this.poi.reduce((p, c) => p += calcDistance(this.center, c) * 2, 0);
	}

	sortFitness(population) {
		return population.sort((a, b) => b.fitness - a.fitness);
	}
	
	createNewGeneration() {
		population = Array(this.populationCount).fill().map(() => new Individual(this));
		return population;
	}

	changeGeneration(population) {
		let newPopulation = [];
		// エリート選択
		let elite = this.sortFitness(population);
		let eliteSurviveRate = 0.01;
		for (let i = 0; i < elite.length * eliteSurviveRate; i++) {
			newPopulation.push(elite[i]);
		}
		// 選択・交叉
		for (let i = 0; i < (population.length * (1 - eliteSurviveRate)) / 2; i++) {
			let parent1 = this.selectByRoulette(population);
			let parent2 = this.selectByRoulette(population);
			if (parent1 != null && parent2 != null) {
				newPopulation = newPopulation.concat(parent1.crossOver(parent2));
			}
		}
		return newPopulation;
	}

	selectByRoulette(population) {
		let totalFitness = population.reduce((p, c) => p += c.fitness, 0);
		let sum = 0;
		let target = Math.random() * totalFitness;
		for (let i = 0; i < population.length; i++) {
			sum += population[i].fitness;
			if (target < sum) {
				return population[i];
			}
		}
		return null;
	}
}

class Individual {
	constructor(env, genes = []) {
		this.env = env;
		// 遺伝子生成 (配列のインデックスが地点、値がトラックを表現)
		this.genes = genes;
		if (this.genes.length <= 0) {
			this.genes = Array(env.poi.length).fill().map(() => Math.floor(Math.random() * env.truck.length));
		}

		// トラック毎地点リスト
		this.perTruckPoi = Array(env.truck.length).fill().map(() => []);
		for (let poiIndex = 0; poiIndex < this.genes.length; poiIndex++) {
			this.perTruckPoi[this.genes[poiIndex]].push(poiIndex);
		}

		// トラック毎距離算出 (次地点が最短になるように地点リスト入替)
		this.perTruckDistance = Array(env.truck.length).fill().map(() => 0);
		for (let truckIndex = 0; truckIndex < this.perTruckPoi.length; truckIndex++) {
			let truckPoi = this.perTruckPoi[truckIndex];
			let truckDistance = 0;
			for (let i = 0; i < truckPoi.length; i++) {
				let minIndex = -1;
				let minDistance = undefined;
				let p = undefined;
				// 初回は拠点スタート、積載可能数の場合は拠点へ戻る距離を加算
				if (i == 0 || i % env.truck[truckIndex].capacity == 0) {
					p = env.center;
					if (i != 0) {
						truckDistance += calcDistance(env.poi[truckPoi[i - 1]], env.center);	
					}
				} else {
					p = env.poi[truckPoi[i - 1]];
				}
				for (let j = i; j < truckPoi.length; j++) {
					let distance = calcDistance(p, env.poi[truckPoi[j]]);
					if (minDistance == undefined || distance < minDistance) {
						minDistance = distance;
						minIndex = j;
					}
				}
				let temp = truckPoi[i];
				truckPoi[i] = truckPoi[minIndex];
				truckPoi[minIndex] = temp;
				truckDistance += minDistance;
			}
			this.perTruckPoi[truckIndex] = truckPoi;
			this.perTruckDistance[truckIndex] = truckDistance;
		}
		
		// 拠点への戻り距離加算
		for (let truckIndex = 0; truckIndex < this.perTruckPoi.length; truckIndex++) {
			if (0 < this.perTruckPoi[truckIndex].length) {
				this.perTruckDistance[truckIndex] += calcDistance(env.poi[this.perTruckPoi[truckIndex].slice(-1)[0]], env.center);
			}
		}

		// トラック毎移動距離の最大値
		this.fitness = (this.env.worstDistance - Math.max.apply(null, this.perTruckDistance)) / this.env.worstDistance;
	}

	crossOver(partner) {
		let genes1 = [];
		let genes2 = [];
		// 交叉 (50%の確立で入替)
		for (let i = 0; i < this.genes.length; i++) {
			if (0.5 < Math.random()) {
				genes1.push(this.genes[i]);
				genes2.push(partner.genes[i]);
			} else {
				genes1.push(partner.genes[i]);
				genes2.push(this.genes[i]);
			}
		}
		let child1 = new Individual(this.env, genes1);
		let child2 = new Individual(this.env, genes2);
		// 突然変異
		if (this.env.mutateRate > Math.random()) {
			child1.mutate();
			child2.mutate();
		}
		return [child1, child2];
	}

	mutate() {
		for (let i = 0; i < this.genes.length * this.env.mutateGeneRate; i++) {
			this.genes[Math.floor(Math.random() * this.genes.length)] = Math.floor(Math.random() * this.env.truck.length);
		}
	}
}

function calcDistance(p1, p2) {
	return Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
}

visualize.js

const MODE_INIIATED = 1;
const MODE_STARTED = 2;
const SCATTER_PLOT_DOT_SIZE = 10;
const SCATTER_PLOT_DOT_MARGIN = 1;
const SCATTER_PLOT_MARGIN = 1;
const RESULT_IMAGE_MARGIN = 5;
const RESULT_IMAGE_GRID_SIZE = 15;
const RESULT_IMAGE_POI_RADIUS = 5;
var environment = null;
var scatterPlot = null;
var resultImage = null;
var text = null;
var generationCount = 0;
var population = [];
var isStop = false;

window.onload = function() {
	init();
}

function init() {
	let poiCount = parseInt(document.getElementById("poiCount").value);
	let populationCount = parseInt(document.getElementById("populationCount").value);
	let mutateRate = parseFloat(document.getElementById("mutateRate").value);
	let mutateGeneRate = parseFloat(document.getElementById("mutateGeneRate").value);
	environment = new Environment(poiCount, populationCount, mutateRate, mutateGeneRate);
	scatterPlot = new ScatterPlot("scatterPlotCanvas");
	scatterPlot.init((environment.poi.length / 2 * (environment.truck.length - 1)) + 1);
	resultImage = new ResultImage("optSolutionCanvas");
	resultImage.init(environment);
	text = new Text("environmentInfoText", "generationInfoText", "resultText");
	text.showEnvironmentInfo();
	text.clearResult();
	setMode(MODE_INIIATED);
}

function start() {
	isStop = false;
	scatterPlot.clear();
	text.clearResult();
	setMode(MODE_STARTED);
	generationCount = 0;
	population = environment.createNewGeneration();
	setTimeout(() => { executeNext(); }, 0);
}

function stop() {
	isStop = true;
}

function executeNext() {
	population = environment.changeGeneration(population);
	generationCount += 1;
	let elite = environment.sortFitness(population)
	if (!isStop) {
		scatterPlot.draw(population);
		resultImage.draw(environment, elite[0]);
		text.showGenerationInfo(generationCount, elite);
		setTimeout(() => { executeNext(); }, 0);
	} else {
		scatterPlot.draw(population, true);
		resultImage.draw(environment, elite[0]);
		text.showResult(environment, elite[0]);
		setMode(MODE_INIIATED);
	}
}

function setMode(mode) {
	let initButton  = document.getElementById("init");
	let startButton  = document.getElementById("start");
	let stopButton  = document.getElementById("stop");
	if (mode == MODE_INIIATED) {
		initButton.disabled = false;
		startButton.disabled = false;
		stopButton.disabled = true;
	} else if (mode == MODE_STARTED) {
		initButton.disabled = true;
		startButton.disabled = true;
		stopButton.disabled = false;
	}
}

class Text {
	constructor(environmentInfoTextId, generationInfoTextId, resultTextId) {
		this.environmentInfoText = document.getElementById(environmentInfoTextId);
		this.generationInfoText = document.getElementById(generationInfoTextId);
		this.resultText = document.getElementById(resultTextId);
	}

	showEnvironmentInfo() {
		this.environmentInfoText.innerHTML = "";
		for (let i = 0; i < environment.poi.length; i++) {
			this.environmentInfoText.innerHTML += "[" + environment.poi[i].x + ", " + environment.poi[i].y + "] ";
		}
	}

	showGenerationInfo(generationCount, population) {
		this.generationInfoText.innerHTML = "Generation " + generationCount + "<br />";
		for (let i = 0; i < 5; i++) {
			this.generationInfoText.innerHTML += "[" + (i + 1)  + "] ";
			this.generationInfoText.innerHTML += "Fitness: " + population[i].fitness.toFixed(5) + ", ";
			this.generationInfoText.innerHTML += "Distance: " + Math.max.apply(null, population[i].perTruckDistance).toFixed(5) + ", ";
			this.generationInfoText.innerHTML += "Genes:" + population[i].genes.join("") + "<br />";
		}
	}

	clearResult() {
		this.resultText.innerHTML = "";
	}

	showResult(env, individual) {
		this.resultText.innerHTML = "";
		for (let i = 0; i < individual.perTruckDistance.length; i++) {
			this.resultText.innerHTML += "<div style='color: " + env.truck[i].color + "'>" + 
				"[Truck " + env.truck[i].id + "] " +
				"Distance: " + individual.perTruckDistance[i].toFixed(5) + ", " +
				"POI: " + individual.perTruckPoi[i].map((p) => "[" + env.poi[p].x + ", " + env.poi[p].y + "]").join(", ") +
				"</div>";
		}
	}
}

class ResultImage {
	
	constructor(id) {
		this.canvas  = document.getElementById(id);
		this.context = this.canvas.getContext("2d");
	}

	init(env) {
		this.clear();
		this.canvas.width = env.poi.length * RESULT_IMAGE_GRID_SIZE + RESULT_IMAGE_MARGIN * 2;
		this.canvas.height = this.canvas.width;
		this.context.strokeStyle = "rgba(200 200 200 / 100%)";
		this.context.lineWidth = 1;
		this.context.beginPath();
		for (let i = 0; i <= env.poi.length; i++) {
			this.context.moveTo(this.convertCoord(i), 0 + RESULT_IMAGE_MARGIN);
			this.context.lineTo(this.convertCoord(i), this.canvas.width - RESULT_IMAGE_MARGIN);
			this.context.moveTo(0 + RESULT_IMAGE_MARGIN, this.convertCoord(i));
			this.context.lineTo(this.canvas.width - RESULT_IMAGE_MARGIN, this.convertCoord(i));
		}
		this.context.stroke();
		this.context.closePath();
		for (let i = 0; i < env.poi.length; i++) {
			this.context.beginPath();
			this.context.arc(this.convertCoord(env.poi[i].x), this.convertCoord(env.poi[i].y), RESULT_IMAGE_POI_RADIUS, 0, Math.PI*2, false);
			this.context.fillStyle = "rgba(0 0 0 / 100%)";
			this.context.strokeStyle = "rgba(0 0 0 / 100%)";
			this.context.fill();
			this.context.stroke();
			this.context.closePath();
		}
	}

	clear() {
		this.context.clearRect(0, 0, this.canvas.width, this.canvas.height);
	}

	draw(env, individual) {
		this.init(env);
		this.context.lineWidth = 2;
		for (let i = 0; i < individual.perTruckPoi.length; i++) {
			let perTruck = individual.perTruckPoi[i];
			this.context.beginPath();
			this.context.strokeStyle = env.truck[i].color;
			this.context.moveTo(this.convertCoord(env.center.x), this.convertCoord(env.center.y));
			for (let j = 0; j < perTruck.length; j++) {
				if (j != 0 && j % env.truck[i].capacity == 0) {
					this.context.lineTo(this.convertCoord(env.center.x), this.convertCoord(env.center.y));
				}
				let poi = env.poi[perTruck[j]];
				this.context.lineTo(this.convertCoord(poi.x), this.convertCoord(poi.y));
			}
			this.context.lineTo(this.convertCoord(env.center.x), this.convertCoord(env.center.y));
			this.context.stroke();
			this.context.closePath();
		}
	}

	convertCoord(coord) {
		return coord * RESULT_IMAGE_GRID_SIZE + RESULT_IMAGE_MARGIN;
	}
}

class ScatterPlot {
	constructor(id) {
		this.canvas  = document.getElementById(id);
		this.context = this.canvas.getContext("2d");
	}

	init(dotCount) {
		this.canvas.width = dotCount * SCATTER_PLOT_DOT_SIZE + SCATTER_PLOT_MARGIN;
		this.canvas.height = this.canvas.width;
		this.clear();
	}

	clear() {
		this.context.clearRect(0, 0, this.canvas.width, this.canvas.height);
	}

	draw(population, isLast = false) {
		this.context.fillStyle = "rgba(255 255 255 / 1%)";
		this.context.fillRect(0, 0, this.canvas.width, this.canvas.height);
		for (let i = 0; i < population.length; i++) {
			this.drawGenes(population[i].genes, "rgba(0 0 255 / 1%)");
		}
		if (isLast) {
			this.drawGenes(population[0].genes, "rgba(255 0 0 / 100%)");
		}
	}
	
	drawGenes(genes, fillStyle) {
		let x = (genes.filter((v, i) => i < genes.length / 2).reduce((p, c) => p += c) * SCATTER_PLOT_DOT_SIZE) + SCATTER_PLOT_MARGIN;
		let y = (genes.filter((v, i) => genes.length / 2 <= i).reduce((p, c) => p += c) * SCATTER_PLOT_DOT_SIZE) + SCATTER_PLOT_MARGIN;
		let size = SCATTER_PLOT_DOT_SIZE - SCATTER_PLOT_DOT_MARGIN;
		this.context.fillStyle = fillStyle;
		this.context.fillRect(x, y, size, size);
	}
}

遺伝的アルゴリズムのデメリットとして実行する度に最適解が変わる可能性がある点はありますが、工場の生産スケジュールやシフト勤務表などのスケジューリング問題をはじめ様々な問題に応用可能です。

利用できる場面は限られるかもしれませんが選択肢の一つとなれば幸いです。

XFacebookLINE
Ｓｋｙ株式会社のソフトウェア開発や製品、採用に関するお問い合わせについては、下記のリンクをご確認ください。
お問い合わせ
ホーム