如何使用 MOPSO 垂直对齐字符?

人工智能 算法 优化 组合学
2021-11-06 15:12:00

我需要使用多目标 PSO 有效地垂直对齐字符。对齐是通过在给定的字符集之间添加空格来实现的。

a b c d e f
b b d h g
c a b f

可能

- a b - c d e f - -
- - b b - d - - h g
c a b - - - - f - -

现在这是一个多目标解决方案。我需要最大化垂直对齐的字符并最小化字符之间的空格量。

我想首先关注如何获得一组字符来表示粒子的位置。这意味着我需要以某种方式将一组可能的字符转换为粒子的位置。如果我能以某种方式实现这一点,那么其余的应该就位。

  • 如何将这些字符集转换为粒子的位置?
  • 这也是最好的方法还是有更好的方法来解决这个问题?
1个回答

您的问题似乎是多序列比对对该问题进行了深入研究,并且根据您的应用程序,有一些快速算法可以在不求助于 AI 或优化的情况下执行得相当好,并且在提供的链接中进行了详细说明。

如果您的问题有很多局部最小值,那么 PSO 可能是一个好方法。当然,本地搜索在过去已被广泛用于此类问题。

您的状态应该由序列列表表示,每个序列都插入一些空格。状态之间的移动可以包括从一个或多个序列中添加或删除空白。两个状态之间的距离可以计算为将每个序列转换为另一个状态的对应序列所需的操作数之和,您可以在线性时间内计算(只需将每对之间所需的添加或删除相加)字母)。

希望能给你一个好的起点!