How to use MOPSO to align characters vertically?

Question

I need to efficiently align characters vertically using Multi Objective PSO. Alignment is achieved by adding spaces in between a given set of characters.

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

Might be

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

Now this is a multi objective solution. I need to maximize the characters that get aligned vertically and minimize the amount of spaces in between the characters.

I wanted to focus firstly on how to get a set of characters to represent a position of a particle. This would mean that I need to somehow transform a possible set of characters into a position of a particle. If I can somehow achieve this then the rest should fall into place.

• How do I transform these set of characters into a position of a particle?
• Also is this the best approach or are there better ways to approach this problem?

Answer 1

Your problem appears to be multiple sequence alignment. That problem is well studied, and depending on your application, there are fast algorithms that can perform quite well without recourse to AI or optimization, and which are detailed in the provided link.

If your problem has a lot of local minima, then a PSO might be a good approach. Certainly local search has been widely used for this kind of problem in the past.

Your state should be represented by a list of sequences, each with some blanks inserted. Movement between states can consist of adding or deleting blanks from one or more sequences. The distance between two states can be computed as the sum of the number of operations needed to transform each sequence to its corresponding sequence in the other state, which you can compute in linear time (just sum up the needed additions or deletions between each pair of letters).

Hope that gives you a good starting place!