[DCVRP] 基于复杂网络的k-opt算法解空间表示(五)

基于复杂网络的k-opt算法解空间表示

如果想提高算法，了解解空间结构是一个很好的突破口。使用 节点表示可行解，边表示可行解之间的领域关系。然后通过计算法复杂网络的基本指标分析算法解空间结构，其目的是得出优秀算法的解空间结构所呈现的特征，基于分析结论设计一个算法使其解空间呈现这种特征，最终使设计的算法性能具有竞争力。 这思路太牛逼了吧 👍

好的算法操作规则对应的复杂网络具有什么样的结构特征？或者说通过分析算法操作规则对应的复杂网络结构特征是否可以评估该算法的求解性能？

一、可行解对应节点标号计算方法

1. 由s[j]获得标号i

这里的$i$的公式错误，应该修改为：

$$\{\begin{array}{l}i=s[n-1]+{\sum }_{j=3}^{n-2}[(s[j]-1)\cdot \frac{N}{j!/2}]\\ s[j]=\{\begin{array}{ll}1,& 0\le j\le 2\\ h(1\le h\le j),& 3\le j\le n-1\end{array}\\ N=(n-1)!/2\end{array}$$

1. 求和公示中改为了$j=3$为初始累加点，因为$0\le j\le 2$在$(s[j]-1)=0$
2. s[j]表示顾客j在标准存在方式中与前$j-1$个顾客及配送中心之间的相对位置，即顾客应插入的“空隙”的位置。至多有j个空隙，故h的取值不超j
3. 空隙的顺序是从右往左数
4. 标号i的范围最小为1，最大为N.

案例 : 假设 $n=6.N=5!/2=60$

标准存放方式	s[0]	s[1]	s[2]	s[3]:20	s[4]:5	s[5]	i
[0,4,3,5,1,2,]	1	1	1	3	4	3	58=3+(4-1)*5+(3-1)*20
[0,5,1,4,3,2]	1	1	1	2	3	5	35=5+(3-1)*5+(2-1)*20
[0,1,2,3,4,5]	1	1	1	1	1	1	1=1+0+0+0+0
[0,5,4,3,2,1]	1	1	1	3	4	5	60=5+(4-1)*5+(3-1)*20

2. 由索引${\pi }_i[j]$获得s[j]

${\pi }_i[j]$ :表示解$\pi +i$中数组索引为j的元素。

设有一个标准存放方式：【0,5,1,4,3,2】----标准存放方式要求仓库为0放在左首

那么有对应关系：

${\pi }_i[0]$	${\pi }_i[1]$	${\pi }_i$