GA Based on the UV-Structure Hypothesis and Its Application to JSP
GA Based on the UV-Structure Hypothesis and Its Application to JSP
复制标题
基于UV结构假设的遗传算法及其在JSP中的应用
DOI：
10.1007/3-540-45356-3_27
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
S. Kobayashi
中科院分区：
文献类型：
--
作者：
Kokolo Ikeda;S. Kobayashi
遗传算法是一种有效的逼近算法，在搜索过程中关注“希望区域”。然而，在更困难的问题中，通常很难在开采和探索之间保持有利的权衡。所有个体往往离开包含全局最优的大谷，而集中到包含局部最优的另一个大谷。本文将常规气体中的这种情况定义为“uv现象”，并将uv结构定义为会引起uv现象的硬质景观结构。我们提出了一种新的遗传模型，即先天分裂模型（ISM），它可以避免紫外线现象。将ISM应用于作业车间调度问题（JSP），该问题被认为是一个全球性的多模态uv结构问题。结果表明，ISM优于所有应用于JSP的著名近似算法。
Genetic Algorithms (GAs) are effective approximation algorithms which focus on "hopeful area" in searching process. However, in harder problems, it is often very difficult to maintain a favorable trade-off between exploitation and exploration. All individuals leave the big-valley including the global optimum, and concentrate on another big-valley including a local optimum often. In this paper, we define such a situation on conventional GAs as the " UV-phenomenon", and suggest UV-structures as hard landscape structures that will cause the UV-phenomenon. We propose Innately Split Model (ISM) as a new GA model which can avoid the UV-phenomenon. We apply ISM to Job-shop Scheduling Problem (JSP), which is considered as one of globally multimodal and UV-structural problems. It is shown that ISM surpasses all famous approximation algorithms applied to JSP.