共查询到19条相似文献,搜索用时 187 毫秒
1.
2.
用混合遗传算法求解图的邻强边着色问题 总被引:1,自引:0,他引:1
图的邻强边着色算法是一个NP完全问题。提出了图的邻强迫着色问题的混合遗传算法。在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域。根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件。实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数。 相似文献
3.
四色和K色图着色问题的瞬态混沌神经网络解法 总被引:3,自引:0,他引:3
首先给出了用神经网络求解四色图着色问题的神经网络结构和能量函数 ,然后采用了具有瞬态混沌特性的神经网络 ( TCNN)来解四色图着色问题 .由于引入具有复杂动态特性的瞬态混沌使得该法具有很强的搜索全局最优解的能力 .仿真结果表明 ,用该法解四色图着色问题总能保证使能量函数收敛到最优解 ,有效避免了用传统的 Hopfield人工神经网络 ( HNN)解此问题时极易陷入局部极小的缺陷 ,并且收敛速度更快 .另外我们还用此法求解了属于 NP-完全问题的 K色图着色问题. 相似文献
4.
针对无训练资源约束的飞行员全动模拟机复训问题,构建双目标整数规划模型对问题进行刻画,通过构造网络流、二部图和加权路等一系列网络规划模型,将原问题转化为最小费用最大流和最长路求解问题,并设计多项式启发式算法对问题进行求解,证明所得解为原问题的非劣解. 最后,实证说明了模型和算法的有效性. 相似文献
5.
基于分布式协商进化算法的多Agent目标冲突消解 总被引:1,自引:0,他引:1
针对多Agent系统研究中的目标冲突消解问题,建立了在多个Agent的局部目标和系统全局目标间进行协调优化的多目标优化模型.在多Agent分布式规划的框架下,提出了一种基于遗传算法(genetic algorithm,GA)的分布式协商进化算法,用于求解多目标规划模型.针对GA搜索中保持解的多样性、提高收敛速度等问题,对选择算子进行了设计.通过仿真实验,证明新的选择算子能有效提高解的质量.最后将该算法应用于部队机动协同路线规划的目标冲突消解问题,验证了其有效性. 相似文献
6.
首先对文献[7]提出的分段广义正交多项式算子(简记为PGOPO)的主要运算规则进行了概括和总结,特别是推导出了非线性函数的PGOPO递推计算公式;其次对一般非线性系统PGOPO算子解及解的收敛性问题进行了分析、研究,证明了PGOPO算子解将收敛于其精确解;最后采用PGOPO算子法对一类含时延的非线性系统进行了分析,并推导出便于使用的递推求解算法.给出的数值算例论证了该算法的有效性. 相似文献
7.
8.
带二维装箱约束的物流配送车辆路径问题 总被引:3,自引:0,他引:3
现实物流活动中大量存在的易损、 易碎物品的运输问题属于带二维装箱约束的物流配送问题, 该问题是二维装箱问题与车辆路径问题这两个经典难题融合之后的一个新问题. 针对这一问题, 在对其进行明确定义的基础上, 建立了数学模型, 提出了解决该问题一个Memetic算法, 对算法中的几个关键算子: 深度优先的启发式装箱方法、染色体的编码方式及其路径分割程序、初始解的生成方法、 交叉算子、局部搜索算子, 进行了详细的阐述. 通过初步的实验, 确定了Memetic算法的最佳参数配置; 然后在Iori提出的30个顾客数在20-199个标准算例上对算法的鲁棒性、求解的质量、以及求解性能等几项指标进行了测试, 并与文献中的求解结果进行了比较. 试验结果表明, 该Memetic算法大大提高了现有算法的性能及求解结果的质量. 相似文献
9.
《系统工程理论与实践》2021,(9)
临近空间平台是一类新兴的空间平台,可用于局部区域的对地观测.本文针对飞艇的特性和用户需求的复杂性,设计了多飞艇多载荷协同对地观测和数据传输体系,考虑常规观测任务的调度,以及应急观测任务的重调度.基于图着色理论(graph coloring theory, GCT),构建多飞艇多载荷协同对地观测和数据传输调度模型.将多飞艇协同对地观测与数据传输任务、任务间的冲突、以及飞艇和地面站分别映射为无向图中的点、边和颜色,从而将问题构建为图着色问题(graph coloring problem,GCP),最大化完成任务总收益的优化目标转换为GCP中最大化着色点收益.提出一种文化基因算法(memetic algorithm,MA),设计基于收益改进的禁忌搜索(Tabu search,TS)算子更新染色体,和对父代染色体中最大收益的连续基因进行遗传的交叉策略.数值实验结果表明,针对不同规模的算例,相较于TS和ILOG CPLEX, MA能够在合理时间内获得更满意的解. 相似文献
10.
11.
Simulated annealing algorithm for detecting graph isomorphism 总被引:2,自引:0,他引:2
Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem (GIP) is a nondeterministic polynomial problem. A simulated annealing (SA) algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability. 相似文献
12.
Graph coloring has interesting real life applications in optimization and network design. In this paper some new results on
the acyclic-edge coloring, f-edge coloring, g-edge cover coloring, (g, f)-coloring and equitable edge-coloring of graphs are introduced. In particular, some new results related to the above colorings
obtained by the authors are given. Some new problems and conjectures are presented. 相似文献
13.
New mixed broadcast scheduling approach using neural networks and graph coloring in wireless sensor network 下载免费PDF全文
Due to the mutual interference and sharing of wireless links in TDMA wireless sensor networks, conflicts will occur when data messages are transmitting between nodes. The broadcast scheduling problem (BSP) is aimed to schedule each node in different slot of fixed length frame at least once, and the objective of BSP is to seek for the optimal feasible solution, which has the shortest length of frame slots, as well as the maximum node transmission. A two-stage mixed algorithm based on a fuzzy Hopfield neural network is proposed to solve this BSP in wireless sensor network. In the first stage, a modified sequential vertex coloring algorithm is adopted to obtain a minimal TDMA frame length. In the second stage, the fuzzy Hopfield network is utilized to maximize the channel utilization ratio. Experimental results, obtained from the running on three benchmark graphs, show that the algorithm can achieve better performance with shorter frame length and higher channel utilizing ratio than other exiting BSP solutions. 相似文献
14.
15.
16.
MINIMUM FILL-IN PROBLEM OF GRAPHS 总被引:1,自引:0,他引:1
YUAN Jinjiang 《系统科学与复杂性》1996,(3)
MINIMUMFILL-INPROBLEMOFGRAPHSYUANJinjiang(DepartmentofMathematics,ZhengzhouUniversity,Zhengzhou450052,China)ZHANGHeping(Depar... 相似文献
17.
一类排序问题的通用模型与最优解 总被引:6,自引:0,他引:6
讨论把n个零件安排给m台机床加工的一类排序问题。在建立了该问题的通用数学模型基础之上,巧妙地把这个排序问题的求解问题转化为指派问题的求解问题,为该排序问题找到了一个理想的通用求解方法。 相似文献
18.
WANG Weifan 《系统科学与复杂性》2000,(2)
1. IntroductionLet G be a graph with vertex set V(G), edge set E(G), maximum degree A(G), minimumdegree 8(G), vertex chromatic number X(G), and edge chromatic number X'(G). G is equitablyk-colorable if V(G) can be pajrtitioned icao k independent sets VI, V2,'', Vk such that llKI III 1 5 1 for all i and j. The such smallest integer k as above is called the equitable chromaticnumber of G, denoted by X= (G). Similaxly we can define the equitable edge chromatic numberof a graph G and d… 相似文献
19.
单机场地面等待问题遗传算法设计 总被引:3,自引:0,他引:3
随着空中交通拥挤问题的日益严重,建立科学合理的空中交通管理系统变得十分迫切,而管理系统的核心一流量管理优化算法的研究就十分重要了,当飞机架次较多时,采用事件驱动型模型会取得较好的求解效果,但原有模型将不同类型飞机的单位延迟费用认为是相同的。从不同飞机有不同的延迟费用这一重要经济因素出发,建立了新的事件驱动型单机场地面等待模型,对模型的求解,设计了改革的序号编码遗传算法,采用上海浦东机场的实际数据进行了仿真,仿真结果表明了模型和算法的有效性。 相似文献