完整代码分为两部分，数据展示和进行计算。为了方便演示，我把所有函数，写成了script标签，放到了html文件里。完全原生，ES6 以上，copy一下，存为html就可以使用。
1、直接打开，你可以看到效果展示
2、按下F12打开控制台， 调用 main(test=false)你可以看到运算过程。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document
</title>
</head>
<body>
<div style="width: 100%;align-items: center;">
<table id="show_t" style="border-spacing: 0; margin: auto;">
</table>
</div>
<button id="do_test" style="border-spacing: 0; margin:0 20%;">换一个
</button>
<script>
/**颜色数组，用来图形化显示，你可以自己选择好的配色 */
COLORS = ["#f99", "#9f9", "#99f", "#ff9", "#9ff", "#f9f", "#fff"];
var arr = [2, 3, 0, 1, 5, 4]; // 测试专用
/** 重置流水线状态和时间记录矩阵
* @param work_state 要复位的工作状态矩阵
* @param c 流程数目
* @param m 每一个流程下可以同时运行的生产线数目
* @param t_maxtr 每一个工件在每个工序上所要消耗的时间
* @param temp_maxtr t_maxtr => temp_maxtr
* @returns temp_maxtr每个工件各个流程的剩余时间记录矩阵
*/
function resetTimeAndState(work_state, c, m, t_maxtr, temp_maxtr) {
var n = t_maxtr[0].length;
// 将每一个机床都复位
for (var i = 0; i < c * m; i++) {
work_state[i] = n; // 用n来表示空闲状态
}
for (var i = 0; i < c; i++) {
for (var j = 0; j < t_maxtr[0].length; j++) {
temp_maxtr[i][j] = t_maxtr[i][j];
}
}
}
/** 计算一个状态量所耗费的时间
* @param {Int16List} work_state 工作状态矩阵
* @param {二维矩阵} temp_maxtr 每个工件各个流程的剩余时间记录矩阵
* @param {Int} c 流程数目
* @param {Int} m 每一个流程下可以同时运行的生产线数目
* @param {Int} n 工件的总数目
* @param {Int16List} arr 工件的加工顺序矩阵
* @returns {Int16List} 返回所用的时间
*/
function calcTime(work_state, temp_maxtr, c, m, n, arr, record) {
var tim = 0; // 使用的总时间
var parts_id = 0;
while (true) {
// 检测是否可以补货
if (parts_id != n) {
for (var i = 0; i < m; i++) {
if (work_state[i] == n) {
work_state[i] = arr[parts_id++];
}
}
}
// 仅当进入测试模式下if条件成立，记录每次一运行时各条流水线上的状态
if (record != null) {
var a = new Array(6);
for (var i = 0; i < 6; i++) {
a[i] = work_state[i];
}
record.push(a.map(item => item));
}
// 每个车间开始工作
for (var i = c * m - 1; i >= 0; i--) {
// 每次循环让所有车间进行一单位的时间
temp_maxtr[Math.floor(i / m)][work_state[i]] = temp_maxtr[Math.floor(i / m)][work_state[i]] - 1;
if (work_state[i] != n) { // 如果这个车间有物品的话
if (temp_maxtr[Math.floor(i / m)][work_state[i]] <= 0) { // 如果这个车间上的东西已经加工完了
if (i >= c * m - m) { // 如果时最后一个车间了
work_state[i] = n; // 就可以把状态设置为空闲了
} else for (var j = 0; j < m; j++) { // 否则就去判断 下一个流程上的车间是否有空闲
if (work_state[(Math.floor(i / m) + 1) * m + j] == n) { // 如果找到空闲了
work_state[(Math.floor(i / m) + 1) * m + j] = work_state[i]; // 就把当前进程放到下一个流水线上
work_state[i] = n; // 并且把状态置成空闲
}
}
}
}
}
// 增加一次时间
tim++;
// 检测是否结束
var is_end = true;
for (var i = 0; i < n; i++) {
if (temp_maxtr[c - 1][i]) {
is_end = false;
break;
}
}
if (is_end) {
return tim;
}
}
}
/** 产生[0, n)范围内的随机整数
* @param {Int} n 随机数上线
*/
function random(n) {
return Math.floor(Math.random() * n);
}
/** 生成一个随机不重复的数列
* @param {Int} len 数组的长度
* @param {Int16Array} arr 结果存储数组
*/
function randomList(len, arr) {
// 生成顺序排列的字符串
for (var i = 0; i < len; i++) {
arr[i] = i;
}
// 打乱
for (var i = len - 1; i > 0; i--) {
var j = random(i); // 生成一个随机数
var tem = arr[j]; // 让最后一位和随机数对应的数字进行交换，然后i--，最后一位向前移动一格
arr[j] = arr[i];
arr[i] = tem;
}
}
/** 初始化自然空间
* @param {*} poor_size 自然空间的种群数目的容纳量
* @param {*} workpiece_num 工件的数目，即每个个体的大小
* @param {*} poor 自然空间种群数目的容纳数组
*/
function poorInit(poor_size, workpiece_num, poor) {
for (var i = 0; i < poor_size; i++) { // 随机生成流程数目
poor[i] = new Array(workpiece_num);
// 对于每一个个体，随机生成其基因序列
randomList(workpiece_num, poor[i]);
}
}
/** 创建一个新的个体， 这个个体由 i 加入部分 j 构成
* @param {二维数组} poor 种群池
* @param {Int} fusion_pos 交叉标志位， 从交叉标记位开始，往后的n个会被替换，n为交换的序列数，是个常量
* @param {Int} workpiece_num 一个体的所拥有的基因数（工件的数目）
* @param {Int} i 初始个体i， i是一个int
* @param {Int} j 初始个体i， j是一个int
* @param {Int} poor_p 目标个体poor_p，新产生的个体数据会被放到这个个体中
*/
function createNew(poor, workpiece_num, fusion_num, fusion_pos, i, j, poor_p) {
var kk_p = fusion_pos; // 记录这个位置，用于更高效的完成循环
// 构建第一个新的数组（个体）
for (var ii = 0; ii < workpiece_num; ii++) {
if (ii < fusion_pos || ii >= fusion_pos + fusion_num) { // 如果是非交换的位置
var is_repeat = false; // 数据重复标志位
for (var jj = fusion_pos; jj < fusion_num + fusion_pos; jj++) {
if (poor[i][ii] == poor[j][jj]) { // 如果要交换的位置检查出了重复
is_repeat = true;
for (var kk = kk_p; kk < fusion_num + fusion_pos; kk++) { // 就从要交换过去的位置里去找一个替换部分不一样的，用这个数来消除重复
var is_repeat2 = false; // 数据重复标志位
for (var iii = fusion_pos; iii < fusion_num + fusion_pos; iii++) {
if (poor[i][kk] == poor[j][iii]) { // 如果在交替部分发生重复就不用考虑这一位了
is_repeat2 = true;
kk_p++; break;
}
}
if (!is_repeat2) { // 如果不是重复的，
poor[poor_p][ii] = poor[i][kk]; // 我们就将这个基因赋值给新的个体
kk_p++; break; // kk的起始位置 +1
}
}
}
}
if (!is_repeat) {
poor[poor_p][ii] = poor[i][ii];
}
} else {
poor[poor_p][ii] = poor[j][ii];
}
}
}
/** 进行个体交叉
* @param {*} poor 种群池
* @param {*} poor_size 种群池的大小（自然环境的容量）（流程顺序方案数目）
* @param {*} surival_size 自然选择下存活的方案数（最优的n种解决方案）
* @param {*} fusion_num 发生交叉时，交换的序列数
* @param {*} workpiece_num 总共要完成的零件数目（也是每个个体的基因数）
*/
function fusion(poor, poor_size, surival_size, fusion_num, workpiece_num) {
var poor_p = surival_size; // 位置标记，要被修改的组的位置
// 将幸存区里的每两个进行交叉
for (var i = 0; i < surival_size; i++) {
for (var j = i + 1; j < surival_size; j++) {
// 随机生成一个位置，将两个个体的一段进行交换
var fusion_pos = random(workpiece_num - fusion_num + 1);
// 交叉生成两个新的个体
createNew(poor, workpiece_num, fusion_num, fusion_pos, i, j, poor_p);
poor_p = poor_p + 1;
createNew(poor, workpiece_num, fusion_num, fusion_pos, j, i, poor_p);
poor_p = poor_p + 1;
}
}
}
/** 变异算法
* @param {*} poor 种群池
* @param {*} poor_size 种群池的大小（自然环境的容量）（流程顺序方案数目）
* @param {*} workpiece_num 总共要完成的零件数目（也是每个个体的大小）
* @param {*} varitarion_rate 变异率，变异率越大，发生变异的可能性越大
*/
function varitation(poor, poor_size, workpiece_num, varitarion_rate) {
for (var i = 1; i < poor_size; i++) { // 从第二大的开始变异
if (Math.random() < varitarion_rate) { // 有一定概率进入变异环节
// 随机选出连个位置
var p1 = random(workpiece_num);
var p2 = random(workpiece_num);
// 交换两个位置里的值
var temp = poor[i][p1];
poor[i][p1] = poor[i][p2];
poor[i][p2] = temp;
}
}
}
// 主函数
function main() {
// 常量定义区
var T_MAXTR = [ // 不同线路对于不同内容初始化
[2, 4, 4, 9, 5, 9],
[4, 9, 2, 5, 2, 4],
[6, 2, 8, 6, 7, 3]
];
var PROCESS_NUM = 3; // 流程数目
var WORKPIECE_NUM = 6; // 总共要完成的零件数目
var WORKSHOP_NUM = 2; // 每一个流程下可以同时运行的生产线数目
var POOR_SIZE = 25;
// 每一波存在的组数
var SUVIVAL_SIZE = 5; // 模拟自然选择，留下最优的n支幸存下来
var VARITATION_RATE = 0.6; // 变异发生的概率
var FUSION_NUM = 3;
// 发生交叉时，交换的序列数
var GENERATION = 50;
// 遗传算法进行多少代
// 初始化内存空间，定义变量
var work_state = new Array(PROCESS_NUM * WORKSHOP_NUM); // 存储流水线状态，用于保存每条流水线上正在加工的工件id
var temp_maxtr = new Array(PROCESS_NUM);
// 用于存储每个工件在加工过程中的剩余时间
for (var i = 0; i < PROCESS_NUM; i++) {
temp_maxtr[i] = new Array(WORKPIECE_NUM);
}
var poor = new Array(POOR_SIZE); // 初始化自然空间个体数目的容纳数组 （总群数）
var scores = new Array(POOR_SIZE); // 存储分数（每个顺序下的时间）
if (test == false) {
// 初始化自然空间
poorInit(POOR_SIZE, WORKPIECE_NUM, poor);
// 进行遗传算法
for (var i = 0; ; i++) {
// 评估每一组的得分
for (var j = i == 0 ? 0 : SUVIVAL_SIZE - 1; j < POOR_SIZE; j++) { // 前四组为SUVIVAL区，上一次已经记录过分数
// 将work_state， 和 temp_maxtr 做归零处理
resetTimeAndState(work_state, PROCESS_NUM, WORKSHOP_NUM, T_MAXTR, temp_maxtr);
// 把得分存到scores里
scores[j] = calcTime(work_state, temp_maxtr, PROCESS_NUM, WORKSHOP_NUM, WORKPIECE_NUM, poor[j]);
}
// 按照评估分数排序(选择排序法)，找到前n个, n为幸存的数目，幸存的数目是我们定义的常量
for (var j = 0; j < SUVIVAL_SIZE; j++) {
for (var k = j; k < POOR_SIZE; k++) {
if (scores[j] > scores[k]) {
// 交换分数
var t1 = scores[j];
scores[j] = scores[k];
scores[k] = t1;
// 交换poor里的内容
var t2 = poor[j];
poor[j] = poor[k];
poor[k] = t2;
}
}
}
console.log("当前最佳时间：" + scores[0]);
console.log("顺序为：" + poor[0]);
// 迭代一定次数后自动停止
if (i == GENERATION) break;
// 交叉 从幸存下来的总群中两两进行交叉，产生新的个体，这里规定交叉必须连续
fusion(poor, POOR_SIZE, SUVIVAL_SIZE, FUSION_NUM, WORKPIECE_NUM);
// 变异 为了保证最后得到的分数是我们测试中出现的最大值，每次选择出的最大值不会参与变异
varitation(poor, POOR_SIZE, WORKPIECE_NUM, VARITATION_RATE);
}
// 遗传过程结束，输出最佳方案和时间
console.log("最佳时间：" + scores[0]);
console.log("顺序为：" + poor[0]);
arr = poor[0];
} else {
// 存储每一个时间的矩阵
var record = [];
// 将work_state， 和 temp_maxtr 做归零处理
resetTimeAndState(work_state, PROCESS_NUM, WORKSHOP_NUM, T_MAXTR, temp_maxtr);
// 把得分存到scores里
var ss = calcTime(work_state, temp_maxtr, PROCESS_NUM, WORKSHOP_NUM, WORKPIECE_NUM, arr, record);
console.log("测试时间为：" + ss);
alert("测试时间为：" + ss);
// 创建一个表格来可视化数据
var table = document.getElementById("show_t");
var inner_html = "";
for (var i = 0; i < PROCESS_NUM * WORKSHOP_NUM + 1; i++) {
inner_html += "<tr class=\'show_tr\'></tr>";
}
table.innerHTML = inner_html;
var trs = document.getElementsByClassName("show_tr");
var j;
for (j = 0; j < PROCESS_NUM * WORKSHOP_NUM; j++) {
for (var i = 0; i < record.length; i++) {
// process.stdout.write("" + record[i][j]);
trs[j].innerHTML += "<td style=\'width:30px;height:30px;background-color:" + COLORS[record[i][j]] + "\'></td>";
}
}
for (var i = 0; i < record.length; i++) {
trs[j].innerHTML += "<td style=\'width:30px;height:30px;background-color:#fff;border-left:1px solid #aaa;\'>" + i + "</td>";
}
// 创建图例
var ul = document.createElement("tr");
inner_html = "<td colspan=" + record.length + "\'>";
for (var i = 0; i < WORKPIECE_NUM; i++) {
inner_html += "<li style=\'color:" + COLORS[i] + ";float:left;margin:10px\'><span style=\'color:#000\'>第" + i + "号工件</span></li>";
}
inner_html += "</td>";
ul.innerHTML = inner_html;
table.appendChild(ul);
}
}
document.getElementById("do_test").onclick = function (){
main(test = false);
main(test = true);
}
main(test = true);
</script>
</body>
</html>
（PS 本题只是测试遗传算法，这么简单的流水线，遍历大法真的爽。题目内容图片来源中国石油大学 智能科学系ppt）
