文档介绍:基因算法优化方法
专利名称:基因算法优化方法
技术领域:
本发明总体上涉及改进的优化方法。特别地,本发明涉及基因算法并且可以用于对高度多模式和欺骗函数进行优化,其一个例子为选择一个传感器网络的传感器个体用于跟踪一个特定目标。
背景技方法,该方法具有以下步骤定义具有n个染色体的基因算法结构的个体,其中每个染色体代表一个传感器,根据想要的
跟踪的特性来定义适合性函数,选择一个或多个个体并将其包含进一个初始总体,对该初始总体执行一种基因算法直到所规定的趋同标准被满足,其中对基因算法的执行具有以下步骤从该总体中选择最适合的个体,以及通过该最适合的个体创造后代,其中仅通过突变来实现对后代的创造,其中在任何一次突变期间仅有i个染色体发生突变,并且其中i的值为从2到n-1。
根据本发明的另一种实施方案,提供了一种用于跟踪目标的传感器网络,包含N个传感器、一种用于N个传感器与控制器进行通信的装置和一个可以通过利用根据本发明的方法从而控制和管理该N个传感器的控制器。
优选地,通过突变、交叉(crossover)或者它们的组合来创造后代。更加优选地,仅通过突变来实现对后代的改变。
优选地,后代的改变发生在i个染色体,其中i的值从2到n-1,其中n是组成一个染色体的基因的数目。更加优选地,i的值为2。
附图简述
图1描述了一个基因算法的总体的一般结构。
图2描述了代表一个基因算法中的步骤的普遍化的流程图。
图3a描述了一种单点、单染色体交叉。
图3b描述了一种双点、单染色体交叉。
图4a描述了一种突变,其中因为突变的概率,仅有一个基因发生了突变。图4b描述了一种突变,其中因为突变的概率,两个基因发生了突变。
图5描述了一种根据本发明的单点、C2交叉。
图6描述了一种根据本发明的C2突变。
图7描述了一种基因算法的结构,该基因算法用于为目标跟踪/标识选择最佳传感器的过程。
图8描述了一种代表根据本发明的一个方面的方法的普遍化的流程图,该方法用于控制和管理一个传感器网络。
图9描述了八种算法在使传感器控制优化方面的性能的平均最佳适合性。
图10描述了图9中所表示的五种算法所进行的优化所必需的时间和有效性。
图11描述了图10中所描述的五种算法改进百分比随时间发生变化的情况。
优选实施方案详述发明装置根据本发明的一种装置包含至少一个传感器、一个处理器,以及一种基因算法。
术语“实体”将被用于对本发明的通篇描述。术语实体应该被理解为广泛地包含多种不同的电子术语,例如任何被用于感应目标或者可以被用于感应目标的传感器,或者在计算机或无线网络中的路由器。实体一般是指,例如可以被用来探测目标的一种特性的传感器。这种特性的例子包含速度、位置、方位、类型(或者标识)、大小。本发明并不限于任意特定类型或数量的传感器。尽管一种优选的实施方案包含小的、便宜的传感器,通篇使用的实体这一术语并不受此限制。可替换地,术语实体还可以指从任意类型的实体(例如一个传感器)中接收到的数据。
优选地,用于本发明的一种实施方案的传感器是这样一种传感器它小于大约2in3(大约33cm3),它的生产和运行成本都比较低,并且可以被容易地部署。这样一种传感器几乎可以是任意类型的传感器,包含但并不限于声学传感器、地震传感器、机械传感器,或者半导体激光传感器。许多公司生产的传感器都可以被用于本发明的一种实施方案,这样的公司的例子包含但不限于Northrop-Grumman、SenTech、Raytheon、BAE、Aliant and Rockwell Sciences Center。
术语“网络”是指多于一个的传感器,这些传感器可以与其它传感器进行通信并且受一个或多个系统或处理器的控制。网络中的一些传感器可能并不能被使用,例如因为它们可能在范围之外,或者它们的电池没电了,或者可能仅仅是它们未被使用但仍然被认为是网络的一部分。网络中的传感器之间的通信可以通过有线或无线方式来实现。只要存在用于控制传感器的一个单独的计划或方法,一个单个的处理器或者多个不同的处理器就可以控制该网络。
术语“处理器”是指一个或多个设备,这一个或多个设备可以确定如何控制和管理传感器以及实际地对传感器进行控制和管理。通常,这种处理器包含可以执行本方法的必要的步骤并可以控制网络的单个传感器的任意可以被使用的处理系统。可以执行处理器功能的处理系统的例子包含但不限于一种500MHz Compaq膝上型计算机。可以理解,控制可编程计算机的软件程序、基于硬件的装置都可以替换地实施本方法并且是本发明的设备的一部分,其中基于硬件的装置包含通用的或由客户设计的集成电路设备,这些通用的或由客户设计的集成电路设备包含集成电路微处理器和永久指令保持存储器。
术语“目标”是指正在被跟踪的物体、动物,或