✨ 本团队擅长数据搜集与处理、建模仿真、程序设计、仿真代码、论文写作与指导，毕业论文、期刊论文经验交流。
（1）混合蚁群算法求解置换流水车间调度问题
置换流水车间调度问题是制造系统中最为经典的调度优化问题之一，其目标是确定一组工件在多台串行机器上的加工顺序，使得某项或多项性能指标达到最优。由于工件在各机器上的加工顺序保持一致的置换约束，问题的解可以用一个工件排列来表示，解空间的规模随工件数量呈阶乘级增长。对于中等规模以上的问题实例，枚举搜索方法在计算时间上已经不可接受，因此需要采用智能优化算法来获取高质量的近似解。本研究提出了一种混合蚁群算法来求解置换流水车间调度问题，该算法在标准蚁群算法的基础上融入多种改进策略，显著提升了算法的求解质量和收敛速度。
在种群初始化阶段，标准蚁群算法通常采用随机方式生成初始解，这种策略虽然能够保证种群多样性，但初始解的质量往往较差，需要较多的迭代次数才能搜索到高质量区域。本研究采用Rajendran构造性启发式规则进行种群初始化，该规则基于工件在各机器上的加工时间信息，按照一定的优先规则逐步构建初始调度方案。通过这种智能初始化策略，算法在迭代开始时就拥有一批质量较好的种群成员，为后续的优化搜索提供了良好的起点。同时，为了避免初始种群过于集中导致的早熟收敛问题，本研究在应用启发式规则时引入了随机扰动机制，确保初始种群具有足够的多样性。
状态转移规则决定了蚂蚁在构建解的过程中如何选择下一个工件，本研究设计了一种基于短作业优先原则的启发式信息计算方法。传统蚁群算法的启发式信息通常只考虑单个工件的加工时间，而忽略了工件之间的相互影响。本研究的改进方法综合考虑候选工件的总加工时间以及其对后续工件等待时间的影响，使得算法在构建解的过程中能够更加准确地评估各候选工件的优劣。在状态转移概率的计算中，启发式信息与信息素浓度共同决定了蚂蚁的选择倾向，两者通过指数参数调节其相对重要性。
信息素更新策略是蚁群算法的核心机制之一，本研究提出了一种自适应的信息素蒸发系数调节方法。传统方法采用固定的蒸发系数，无法根据搜索进程的变化自动调整信息素的更新强度。本研究设计了一种基于指数函数的动态蒸发系数，在算法运行初期蒸发系数较大以促进全局探索，随着迭代次数增加蒸发系数逐渐减小以强化局部开发。此外，本研究还引入了精英保留策略，只有当前迭代的最优蚂蚁才能在其经过的路径上释放额外的信息素，这种策略能够加速优质解区域的信息素积累，引导后续搜索向最优解方向集中。
局部搜索能力的强弱直接影响算法最终解的质量，本研究设计了一种基于整数序列集合的局部搜索算法。该算法维护一个包含多种邻域移动操作的集合，包括插入移动、交换移动和逆序移动等。在每次局部搜索过程中，算法从当前解出发，依次尝试集合中的各种移动操作，如果发现改进解则立即接受并继续搜索，否则尝试下一种操作。这种多邻域联合搜索策略能够更加充分地挖掘当前解的邻域空间，发现更多的改进机会。为了避免局部搜索陷入局部最优，本研究还引入了模拟退火的接收准则，以一定概率接受劣解以实现搜索空间的跳跃。
（2）动态多种群蚁群算法求解阻塞流水车间调度问题
阻塞流水车间调度问题是置换流水车间问题的一种变体，其主要特点是机器之间不存在缓冲区，当一个工件在某台机器上加工完成后，如果下游机器被占用，则该工件必须继续停留在当前机器上，从而阻塞后续工件的加工。这种阻塞约束使得问题的求解变得更加复杂，需要设计专门的算法来应对。本研究在深入分析种群间协同进化机制的基础上，提出了一种动态多种群蚁群算法来求解阻塞流水车间调度问题，通过多种群协作和动态信息交换来提升算法的全局搜索能力和解的质量。
本研究将蚁群划分为三种类型：精英种群、搜索种群和变异种群。精英种群由算法运行过程中发现的最优个体组成，负责维护和传承高质量的解信息。搜索种群是算法的主要搜索力量，多个搜索种群在不同的解空间区域并行探索，增加了发现全局最优解的可能性。变异种群是一种特殊的动态种群，在算法运行到一定阶段后才被创建，用于跳出当前搜索可能陷入的局部最优区域。变异种群的生成方式具有创新性：从各搜索种群和精英种群中提取较差个体，对其进行重新初始化后形成变异种群，这种策略既利用了现有搜索信息又引入了新的探索方向。
种群间的信息交流是多种群协同进化的关键机制，本研究设计了分阶段、差异化的信息交换策略。在算法运行初期，多个搜索种群之间首先按照轮换规则进行优质解的互换，每个种群将自身的最优解传递给相邻种群，同时接收其他种群的优质解，这种横向信息流动有助于促进各种群之间的知识共享。经过若干次迭代后，从所有搜索种群中选出全局最优解传递给精英种群，精英种群则将一个较差解传给相应的搜索种群以维持种群多样性，这种纵向信息流动实现了精英解的集中保存和次优解的循环利用。
变异种群生成后，采用特殊的信息交换规则与精英种群进行互动。在每次迭代结束后，变异种群将自身发现的最优解与精英种群的当前最优解进行比较，如果变异种群的解更优则替换精英种群的最优解，反之则精英种群将一个较差解传递给变异种群以补充其种群成员。这种竞争性的信息交换机制既保证了最优解的实时更新，又维持了变异种群持续探索新区域的能力。精英种群在每次迭代后对其保存的最优解和次优解执行局部搜索，通过精细化搜索进一步提高解的质量。
（3）改进生物地理学算法求解有限缓冲流水车间调度问题
生物地理学优化算法是一种模拟物种在不同栖息地之间迁徙行为的智能优化算法，具有参数少、易实现的特点。然而，标准生物地理学算法在处理组合优化问题时面临编码表示和算子设计的挑战，需要进行针对性的离散化改造。本研究针对以总流水时间为目标的中间存储有限流水车间调度问题，提出了一种离散化生物地理学算法，通过重新设计编码方式、迁徙操作和变异操作来适应问题的离散特性。
编码设计是离散化改造的基础，本研究采用基于工件排列的向量编码方式。每个个体用一个长度等于工件数量的整数向量表示，向量的第k个位置存储的是加工顺序中第k个被加工的工件编号。这种编码方式直观地反映了工件的加工顺序，便于计算调度目标函数值，同时也为后续的进化操作提供了操作对象。适应度函数采用总流水时间的倒数形式，使得适应度值越大对应的解越优，符合标准生物地理学算法的适应度越大迁入率越高的设定。
种群初始化采用NEH和NEHWPT两种启发式规则相结合的策略。NEH规则是求解流水车间调度问题最为著名的构造性启发式之一，它首先按照工件总加工时间的降序对工件排序，然后依次将每个工件插入当前部分序列的最佳位置。NEHWPT规则则在NEH的基础上考虑了加权加工时间因素，对于以总流水时间为目标的问题往往能够获得更好的初始解。本研究将部分种群成员用NEH规则初始化，另一部分用NEHWPT规则初始化，再辅以随机初始化的个体，形成质量与多样性兼具的初始种群。
迁徙操作是生物地理学算法的核心进化机制，本研究采用余弦函数作为迁徙率模型，相比于传统的线性模型能够提供更加平滑的适应度与迁徙率映射关系。在具体的迁徙实现上，本研究提出了一种基于两点式交叉的种群迁徙算法。当确定某个个体需要接收来自高适应度个体的信息时，随机选择两个切点将父代个体分割为三段，然后按照一定规则从高适应度个体中继承相应的工件安排。这种两点式迁徙操作既能有效传递优秀个体的特征信息，又能保持一定程度的解结构变化。
import numpy as np from itertools import permutations def calculate_makespan(sequence, processing_times): n_jobs, n_machines = processing_times.shape completion_times = np.zeros((n_jobs, n_machines)) for i, job in enumerate(sequence): for m in range(n_machines): if i == 0 and m == 0: completion_times[i, m] = processing_times[job, m] elif i == 0: completion_times[i, m] = completion_times[i, m-1] + processing_times[job, m] elif m == 0: completion_times[i, m] = completion_times[i-1, m] + processing_times[job, m] else: completion_times[i, m] = max(completion_times[i-1, m], completion_times[i, m-1]) + \ processing_times[job, m] return completion_times[-1, -1] def calculate_total_flowtime(sequence, processing_times): n_jobs, n_machines = processing_times.shape completion_times = np.zeros((n_jobs, n_machines)) for i, job in enumerate(sequence): for m in range(n_machines): if i == 0 and m == 0: completion_times[i, m] = processing_times[job, m] elif i == 0: completion_times[i, m] = completion_times[i, m-1] + processing_times[job, m] elif m == 0: completion_times[i, m] = completion_times[i-1, m] + processing_times[job, m] else: completion_times[i, m] = max(completion_times[i-1, m], completion_times[i, m-1]) + \ processing_times[job, m] return np.sum(completion_times[:, -1]) def neh_heuristic(processing_times): n_jobs = processing_times.shape[0] total_times = np.sum(processing_times, axis=1) sorted_jobs = np.argsort(-total_times) sequence = [sorted_jobs[0]] for j in range(1, n_jobs): job = sorted_jobs[j] best_pos = 0 best_makespan = float('inf') for pos in range(len(sequence) + 1): trial = sequence[:pos] + [job] + sequence[pos:] makespan = calculate_makespan(trial, processing_times) if makespan < best_makespan: best_makespan = makespan best_pos = pos sequence = sequence[:best_pos] + [job] + sequence[best_pos:] return sequence def hybrid_aco(processing_times, n_ants=20, max_iter=100, alpha=1.0, beta=2.0, rho=0.1): n_jobs, n_machines = processing_times.shape pheromone = np.ones((n_jobs, n_jobs)) / n_jobs best_sequence = neh_heuristic(processing_times) best_makespan = calculate_makespan(best_sequence, processing_times) heuristic = 1.0 / (np.sum(processing_times, axis=1) + 1e-10) for iteration in range(max_iter): all_sequences = [] all_makespans = [] for ant in range(n_ants): sequence = [] remaining = list(range(n_jobs)) while remaining: if not sequence: probs = heuristic[remaining] ** beta else: last = sequence[-1] probs = (pheromone[last, remaining] ** alpha) * (heuristic[remaining] ** beta) probs = probs / np.sum(probs) next_job = np.random.choice(remaining, p=probs) sequence.append(next_job) remaining.remove(next_job) makespan = calculate_makespan(sequence, processing_times) all_sequences.append(sequence) all_makespans.append(makespan) if makespan < best_makespan: best_sequence = sequence.copy() best_makespan = makespan evap_rate = rho * np.exp(-iteration / max_iter) pheromone *= (1 - evap_rate) best_ant = np.argmin(all_makespans) for i in range(len(all_sequences[best_ant]) - 1): j1, j2 = all_sequences[best_ant][i], all_sequences[best_ant][i+1] pheromone[j1, j2] += 1.0 / all_makespans[best_ant] improved = True while improved: improved = False for i in range(n_jobs): for j in range(i+1, n_jobs): new_seq = best_sequence.copy() new_seq[i], new_seq[j] = new_seq[j], new_seq[i] new_makespan = calculate_makespan(new_seq, processing_times) if new_makespan < best_makespan: best_sequence = new_seq best_makespan = new_makespan improved = True return best_sequence, best_makespan def discrete_bbo(processing_times, pop_size=30, max_iter=100, objective='flowtime'): n_jobs = processing_times.shape[0] calc_obj = calculate_total_flowtime if objective == 'flowtime' else calculate_makespan population = [] neh_seq = neh_heuristic(processing_times) population.append(neh_seq) for _ in range(pop_size - 1): seq = np.random.permutation(n_jobs).tolist() population.append(seq) fitness = [1.0 / (calc_obj(seq, processing_times) + 1e-10) for seq in population] best_idx = np.argmax(fitness) best_solution = population[best_idx].copy() best_obj = calc_obj(best_solution, processing_times) for iteration in range(max_iter): sorted_idx = np.argsort(fitness)[::-1] immigration_rate = np.array([(pop_size - i) / pop_size for i in range(pop_size)]) emigration_rate = np.array([i / pop_size for i in range(pop_size)]) new_population = [] for i in range(pop_size): if np.random.rand() < immigration_rate[sorted_idx[i]]: emigrant_probs = emigration_rate / np.sum(emigration_rate) emigrant_idx = np.random.choice(pop_size, p=emigrant_probs) emigrant = population[sorted_idx[emigrant_idx]] p1, p2 = sorted(np.random.choice(n_jobs, 2, replace=False)) new_seq = population[sorted_idx[i]].copy() segment = emigrant[p1:p2+1] remaining = [j for j in new_seq if j not in segment] new_seq = remaining[:p1] + segment + remaining[p1:] new_population.append(new_seq) else: new_population.append(population[sorted_idx[i]].copy()) for i in range(pop_size): mutation_rate = 1 - fitness[sorted_idx[i]] / max(fitness) if np.random.rand() < mutation_rate * 0.3: p1, p2 = sorted(np.random.choice(n_jobs, 2, replace=False)) new_population[i][p1:p2+1] = new_population[i][p1:p2+1][::-1] population = new_population fitness = [1.0 / (calc_obj(seq, processing_times) + 1e-10) for seq in population] current_best_idx = np.argmax(fitness) current_best_obj = calc_obj(population[current_best_idx], processing_times) if current_best_obj < best_obj: best_solution = population[current_best_idx].copy() best_obj = current_best_obj return best_solution, best_obj if __name__ == "__main__": np.random.seed(42) n_jobs, n_machines = 20, 5 processing_times = np.random.randint(1, 100, (n_jobs, n_machines)) aco_seq, aco_makespan = hybrid_aco(processing_times) print(f"ACO Makespan: {aco_makespan}") bbo_seq, bbo_flowtime = discrete_bbo(processing_times, objective='flowtime') print(f"BBO Total Flowtime: {bbo_flowtime}") bbo_seq2, bbo_makespan = discrete_bbo(processing_times, objective='makespan') print(f"BBO Makespan: {bbo_makespan}")👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇
