用于解决一类现实组合优化问题的算法开发环境的方法和装置

技术领域

本发明涉及集成的问题解决领域。更具体地，本发明涉及一种系统，其用于利用任何其他形式的启发式或超启发式搜索快速开发具有混合可能性的遗传算法，以解决组合优化问题的特定类的现实应用。实现这种定制算法的方法只需对编码花很少的精力，却交出高效解决给定类的问题的算法形式的结果。在一种方式中，本发明涉及配置用于提供供应链管理的解决方案的遗传算法(GA)，但是应理解的是本发明并非仅限于该用途。

背景技术

本说明书中的讨论是由于发明人认识到某些现有技术的问题而产生。

在最近几十年，现实情况中组合优化的应用日益增多。经常地，这些现实情况问题对应于已在学术中被分类的多类组合优化问题。随着问题范围的扩大，这些问题的计算复杂度趋向于指数增长。这些问题属于被称之为NP-hard的一类问题。NP-hardness使得这些优化问题通过精确的穷举方法或确定性的算法是难以计算的。因此，出现很多基于启发式和超启发式的方法以满足为这些问题配置快速和高效的解决方案的需要。这些方法被分类为逼进解决方法，且算法通常在本质上是非确定性的。例子可包括进化计算、模拟退火、禁忌搜索、神经网络、自适应贪婪方法，以及最近的诸如蚁群优化的群集智能方法。

但是，为了利用这些算法的能力解决现实问题，通常需要花相当多的精力来设计、实现和定制算法以适合问题领域的具体性质。常规算法开发过程往往需要大量的繁重且低效的低级代码生成和修改。考虑到这些，越来越多的人转为开发平台以使算法开发和问题解决过程更加容易。特别关心的是涉及进化算法的这类问题解决环境，所述进化算法已经由于其普遍性和健壮性而吸引了很多的注意。

在美国专利No.6,112,126中，提出了一种自适应的面向对象的优化系统，其包括目标搜寻(goal-seeking)智能软件对象。但是，本发明仅专用于解决过程控制优化。它对一般的问题解决没有多少帮助。

在美国专利No.6,263,352、美国专利No.6,086,617中，提出了Epogy过程集成和设计优化软件以及递阶进化工程设计系统(HEEDS)软件、具有包括遗传算法的各种优化技术的问题解决环境。它们提供了友好用户界面以研究用于解决所提出的不同的优化问题的各种优化工具。这一类平台促进了算法设计过程并因此大大提高了解决问题的效率。但是，这些软件工具实质上是模拟环境。虽然在这些环境下各种算法可以被配置和高效地执行，但该执行依赖于整个系统。虽然是总控问题解决算法，但对于需要嵌入的实时解算器的应用，这一类环境不提供配置高效独立程序的灵活性。在美国专利No.5,581,657中，在特定遗传算法中，引入了分布计算技术以增强现有的优化技术解决问题的能力。但是，因为它实质上仍是算法执行者，不能满足快速生成独立问题解决算法的需要。

在美国专利No.6,286,017中，提出了一种帮助用户快速生成独立应用的图形环境。它包括由表格处理软件(spreadsheet)管理的模块库，并采取其他软件重用技术。用户能利用它提供的友好的图形用户界面(GUI)从库中获得过程。基于所选的过程，自动生成独立的应用。但是，该发明仅针对编程事件。它不涉及任何算法设计知识。因此，当需要开发诸如超启发法的复杂算法时，它可能不满足解决方法的需要。

TOMLAB是MATLAB中的普通优化环境。它实质上是MATLAB工具箱，其封装了各种优化过程，该过程包括类似遗传算法的复杂的超启发法。它大概使用户很容易获得集成的过程和例程以建立源代码形式的应用。但是，它不能自动生成源代码且用户必须处理功能编程语言，即MATLAB编程语言。这对可能不熟悉MATLAB语言的用户是个大障碍。而且，它需要昂贵的第三方软件环境，即MATLAB，的支持。

进化算法的简单规范(EASEA)是专用于进化算法(EA)规范的高级脚本语言。它从公知的EA库中获取各种EA过程和例程：GALib和EO。用户用EASEA语言编写.ez文件以配置进化算法。然后EASEA编译器将.ez文件编译成C++文件。然后所生成的C++文件被编译并与对应的库链接以产生执行原始.ez文件中指定的进化算法的可执行文件。这样，可避免算法开发中最繁重的代码生成工作。因此，可以显著提高应用开发的效率。但是，EASEA以及其他类似的语言，即进化算法建模语言(EAML)，仍然是一种基于文本形式的语言，虽然它比任何功能编程语言具有更高的抽象度。这两种脚本语言都需要专门设计的编译器来将脚本语言转换成功能编程语言。而且，普通用户必须熟悉该语言的语法。

本发明书中文档、设备、行为或知识的任何讨论都被包括以解释本发明的上下文。不应当认为是承认任何所述材料形成为部分现有技术的基础或此处的公开内容和权利要求的优先权日或之前的相关技术中的普通公知常识。

发明内容

大体上，本发明提供了一种用于解决至少一个组合优化问题的配置搜索算法的过程组件的数据结构，以及使用所述结构的方法和装置。所述数据结构是具有与配置过程组件的方式相关联的节点的树。数据树的遍历对应于配置过程组件的步骤。

通过遍历算法而引导用户逐节点地经过树结构，在每个节点在可用的选项间做选择。某些所述选项包括确定遍历算法采取哪一路径经过树结构的选项。这使通用的软件系统成为可能，该软件系统提供开放且友好的界面；使用户能够根据解决方法而快速地配置进化算法并自动地优化算法的配置以解决一类组合优化问题。所提到的这类问题是那些其解决方案可被表示为排列串结构(permutation string structure)的问题。

本发明的第一个具体表达是配置用于解决至少一个组合优化问题的搜索算法的一个或多个过程组件的一种方法，所述方法对每个过程组件使用代表配置该过程组件的方式的对应数据结构，

所述数据结构包括在树结构中被关联到一起的多个节点，多个所述节点代表将要做出的用于配置过程组件的相应选择。

所述方法包括通过遍历算法遍历树结构来配置所述过程组件，其中多个所述节点依次被标记为当前节点，以及，在当前节点代表将要做出的用于配置过程组件的选择时，接收做出当前节点所代表的选择的输入。

本发明的可替换点可以用所述方法中使用的数据结构来表示。

特别地，本发明的可替换表达是一种配置用于解决至少一个组合优化问题的搜索算法的过程组件所使用的数据结构，其中所述数据结构包括代表算法的过程组件的可能配置的树结构，所述树结构包括：

代表算法的组件的主节点；

起源于所述主根节点的一个或多个第一节点，每个第一节点是(i)代表配置过程组件的一个或多个选项的变化节点(variation node)，或者(ii)代表配置过程组件所需的一个或多个选择的属性节点(property node)；

一个或多个第二节点，每个第二节点起源于所述第一节点之一，其中如果第二根节点起源于变化节点，所述第二节点代表对应选项之一，以及如果第二根节点起源于属性节点，所述第二节点代表选择之一。

本发明的可替换表达是一种配置用于解决组合优化问题的搜索算法的过程组件所使用的数据结构，其中所述数据结构包括代表算法的组件过程的可能配置的树结构，

所述树结构包括在分层结构中链接在一起的多个子树；

每个子树与过程组件的对应方面相关联，以及是以下之一：

与配置过程组件的对应方面的多个选项相关联的变化子树，或

与过程组件的对应方面所需的一个或多个选择相关联的属性子树。

在本发明的另一方面中提供一种在配置用于解决组合优化问题的算法中所使用的数据格式，其中所述数据格式包括树结构，所述树结构包括：

主根节点；

起源于所述主根节点的至少一个第一根节点；

起源于所述第一根节点的至少一个第二根节点，其中所述至少一个第二根节点包括下列之一：

a)所述第一根节点的变化；

b)指向所述第一根节点的一个或多个变化的节点；

c)所述第一根节点的每个变化所共有的属性；

d)指向所述第一根节点的每个变化所共有的属性的节点；

e)另一个第一根节点；

f)另一个第二根节点；

g)NULL。

在另一方面中，本发明提供一种配置用于生成解决至少一个组合优化问题的算法的启发式搜索过程的至少一个过程组件的方法，所述至少一个过程组件包括具有变化节点和属性节点的树结构，所述方法包括根据以下步骤遍历所述树结构：

a)选择包含起源于所述树的主根节点的根节点的子树；

b)选择起源于所述根节点的一个节点；

c)确定所选的一个节点是叶节点还是另一子树的根节点；

d)如果所选的一个变化节点是另一子树的根节点，对所述另一子树重复步骤b)和c)；

e)如果所选的一个节点是叶节点，返回所述叶节点的值以配置过程组件；

其中执行步骤a)到e)以使得变化节点优先于属性节点。

优选地，所述算法可包括遗传算法和/或混合遗传算法。

在另一方面中，本发明提供一种配置用于解决优化问题的遗传算法的方法，所述方法包括步骤：

a)提供代表遗传算法的各个可能的配置的初始的染色体群体；

b)基于适应度(fitness)函数评价染色体群体以指定群体的成员作为父代；

c)对父代执行一个或多个遗传操作以繁殖后代；

d)用后代和父代一起更新群体；

e)确定所更新的群体是否满足结束条件；

f)重复步骤a)到e)直到满足结束条件。

在优选方面中，本发明提供适于配置用于生成解决至少一个组合优化问题的算法的启发式搜索过程的至少一个过程组件的设备，所述设备包括适于根据预定的指令集操作的处理器装置(means)，结合有所述指令集的所述设备适于执行此处公开的方法。

在另一优选方面中，本发明提供一种计算机程序产品，该产品包括：

计算机可用介质，该介质包括包含在所述介质上的计算机可读程序代码和计算机可读系统代码，其用于在数据处理系统中配置用于生成解决至少一个组合优化问题的算法的启发式搜索过程的至少一个过程组件，所述计算机程序产品包括：

所述计算机可用介质中的计算机可读代码，其用于执行此处公开的方法中的任何一个方法的方法步骤。

本发明的优选实施例使得本发明可以满足总控解决方案提供者的需要和挑战。所述优选实施例为开发者提供了平台以通过集成的问题解决环境来配置用于高效解决现实优化问题的算法。不具有关于算法设计的很深的背景知识和具有中等水平的编程技能的用户或系统集成商，可使用该平台配置和生成混合有环境中提供的任何启发法或超启发法的遗传算法。结果是基于很高水平的用户说明书而生成的独立程序。通过将问题领域具体特征引入源代码，用户需要很少的编码精力就可定制生成的解决各种关心的问题的程序。这样，算法开发的效率得到了显著的提高。本发明特别适用于这类具有排列解析结构(solution structure)的优化问题，因为很多现实问题的解决方案可归结为排列串。

本发明的其他方面和优选方面被公开在说明书中和/或限定在所附的权利要求中，形成本发明的说明的一部分。

特别是，本发明的某些实施例提供了许多优点和/或有益的结果，如下：

1、用于设计和开发解决复杂优化问题的高效算法的综合问题解决环境。

2、所述环境与用于设计和配置混合遗传算法的变量的开发平台有关。

3、遗传算法开发平台致力于一类广泛适用的组合优化问题，由此解析结构可用排列串代表。

4、所述遗传算法开发平台还包括基于模块的过程库。

5、所述基于模块的库采用“左变化-右属性”树结构的新的分层树结构作为管理和组织过程模块的方法。

6、所述遗传算法开发平台还包括用于配置混合遗传算法的高级图形用户界面。

7、所述图形用户界面实现了用于算法配置的树结构的可视化。

8、所述“左变化-右属性”树结构还包括“左变化-右属性”树遍历规则。这种遍历规则，与深度优先树遍历规则一起，引导用户通过沿着分层树和子树遍历而完成算法的配置。

9、所述基于模块的库基于面向对象的构架。

10、源代码生成器，其能基于用户指定的配置来生成独立程序，并且基于面向对象的基于模块的库和以上树结构而被执行。

11基于目标搜寻的程序定制由源代码生成器产生，以解决各种优化问题。

通过下面给出的详细说明，本发明的其他适用范围将变得明显。但是应理解，详细说明和具体实施例虽然表明了本发明的优选实施例，但仅通过示例性方式给出，因为通过这些详细说明，本发明的主旨和范围中的各种改变和修改对本领域技术人员而言是很显然的。

附图说明

通过参考结合附图的优选实施例的以下说明，相关领域技术人员可以更好地理解本申请的其他公开内容、目的、优点和方面，其仅通过示例性的方式给出，且因此不是对本发明的限制，其中：

图1显示了遗传算法(或混合遗传算法)流程图的一些可能的功能构造，由可被作为本发明的实施例的方法和装置配置的搜索算法中的过程组件组成。

图2显示了本发明的一个实施例，其是组件“后代生产者”的分层树结构。

图3显示了本发明的一个实施例，其是组件“个体操作”的树结构。

图4显示了本发明的一个实施例，其是组件“群体初始化”的树结构。

图5显示了本发明的一个实施例，其是组件“群体更新”的树结构。

图6显示了本发明的一个实施例，其是组件“群体评价”的树结构。

图7显示了本发明的一个实施例，其是组件“结束条件”的树结构。

图8示出了组件“后代生产者”的示例配置的流程。

图9显示了根据结构观点而将任一遗传算法分成三个组件。