<p>这是一个老问题,但我想分享我的方法。
我有一个CVRP(电容车辆路径问题)任务。我的启发式算法产生了几个不同的图,以便找到一个解决方案。
为了不陷入局部最优,我采用了放松和修复程序。</p>
<p>在这一点上,我不得不过滤掉太相似的溶液。
由于大多数启发式方法在局部搜索过程中使用系统的邻域变化来提供解决方案,所以<code>Edit</code>距离(<code>Levenshtein distance</code>)对我来说是完美的。<code>Levenshtein</code>算法的复杂度为<code>O(n*m)</code>,其中n和m是两个字符串的长度。因此,通过图形节点和路由的字符串表示,我能够计算出相似度。可以将<code>edit operations</code>视为<code>neighborhood operations</code>,因此可以将其视为搜索空间距离(而不是解空间距离)。</p>
<p>牺牲一些速度的更好的/通用方法是<code>Needleman-Wunsch</code>算法。<code>Needleman-Wunsch</code>是一种混合相似性度量,它推广了Levenshtein距离并考虑了两个字符串之间的全局对齐。具体来说,它是通过为两个输入字符串之间的每个对齐指定一个分数并选择最佳对齐的分数(即最大分数)来计算的。两个字符串之间的对齐是其字符之间的一组对应关系,允许有间隙。</p>
<p>例如:</p>
<pre><code>import py_stringmatching as sm
nw = sm.NeedlemanWunsch(gap_cost=0.5, sim_func=lambda s1, s2: (0.0 if s1 == s2 else 1.0))
print('\nNeedleman-Wunsch: ', nw.get_raw_score('045601230', '062401530'))
</code></pre>
<p>在示例中,可以使用自定义的Levenshtein算法。</p>
<p>Git中存在Levenshtein的快速实现(使用Cython、Numpy等)。<br/>
一个不错的库是<a href="https://anhaidgroup.github.io/py_stringmatching/v0.3.x/Levenshtein.html" rel="nofollow noreferrer">py_stringmatching</a>,它包含以下相似算法列表:</p>
<ul>
<li>仿射间隙</li>
<li>袋距</li>
<li>余弦</li>
<li>骰子</li>
<li>伊迪迪斯</li>
<li>广义Jaccard</li>
<li>汉明距离</li>
<li>雅卡</li>
<li>雅罗</li>
<li>雅罗温克勒</li>
<li>左旋血凝素</li>
<li>蒙古埃尔坎</li>
<li>女红</li>
<li>重叠系数</li>
<li>部分比率</li>
<li>部分标记排序</li>
<li>比率</li>
<li>史密斯·沃特曼</li>
<li>软TF/IDF</li>
<li>Soundex公司</li>
<li>特遣部队/国际国防军</li>
<li>标记排序</li>
<li>特沃斯基指数</li>
</ul>