Fig. 1. (a)机器人
最后一个节点是目标节点。如果一条路径的每一段都通过了空白网
格,那么只有该路径可以被认为是可行路径,否则它就是不可行路
径。
1
(
b
)路径(
1
,
10
,
14
,
36
)是可行路径,而路径(
1
,
6
,
36
)是不可行路径。
3.1.3.
初始种群
初始种群中的个体或路径(也称为染色体)是随机生成的,没有
一个个体是不可行的。不可行项的存在对于一个特定的问题,随着人
口规模的增加,搜索过程变得更加多样化,但它引入了额外的计算成
本。因此,选择种群规模以保持搜索过程中的多样性和计算成本之间
的平衡是非常重要的此外,在文献中不存在为给定环境选择适当的种
群大小值的标准指南也不存在任何可以通过仅检查环境的大小、源和
目的地的位置、形状、大小以及环境中存在的障碍物的位置来测量环
境的复杂性水平的标准除此之外,不存在这样的方法,其产生用于特
定复杂性水平的环境的适当的群体大小。因此,唯一的解决方案是为
环境使用不同的种群大小,并选择在可接受的计算时间限制内提供最
佳结果同样,我们对每个环境使用了不同的种群大小,并报告了我们
在计算时间方面获得可接受结果的种群大小。
3.1.4.
健身
适应度函数用于评价群体中染色体设
P
是从起始结点到目标结点的
包含
n
个结点的路径由于距离已被视为优化标准,因此目标函数
f
(如
等式(
1
)所示)(
1
)路径
P
需要最小化。
X
n
q
2
2
注意,由于惩罚分数增加了适应度值,因此选择不可行路径的概率降
低。
3.1.5.
遗传算子
有三个遗传算子。它们是选择,交换和突变.这三个遗传算子在下文
中进行了描述。
3.1.5.1.
选择
.
选择算子是基于
“
适者生存
”
的概念换句话说,特定染色
体的选择概率与该染色体的适应度值成比例从群体中选择染色体以创
建交配池,其大小与群体的大小相同
3.1.5.2.
交叉。
在交叉中,两个亲本染色体之间交换信息,并为下一代
产生两个后代。在这项工作中,我们使用了单点交叉,其中单点是从
除了起始节点和目标节点之外长度较短的父染色体中随机选择的。否
则,在执行交叉之后,可能存在在子弹簧之一中具有多个开始节点或
目标节点而在另一子弹簧中没有开始节点或目标节点的机会