I'm trying to implement a particle swarm optimization algorithm for a cryptanalysis local search to find the key of a simple substitution cipher.
I understand the theory of how this method work and have implemented most of the algorithm, but I just can't figure out how to calculate the velocity.
Particle Class:
public class Particle extends Alphabet {
public Vector velocity = new Vector();
public char[] pbest;
public Particle() {
this.Scramble();
}
public char[] getPosition() {
return this.getAlphabet();
}
}
Swarm Class:
public class ParticleSwarm {
public List<Particle> swarm = new ArrayList<>();
private Fitness fitness = new Fitness();
public void randomSwarm(int swarmSize) {
for(int i = 0; i < swarmSize; i++) {
swarm.add(new Particle());
}
}
public Particle getBestParticle() {
Particle swarmBest = new Particle();
double bestScore = 0;
for(int i = 0; i < swarm.size(); i++) {
double newScore = fitness.score(swarm.get(i).getPosition());
if(newScore >= bestScore) {
bestScore = newScore;
swarmBest = swarm.get(i);
}
}
return swarmBest;
}
}
A particle is an extension of an alphabet class I made for another algorithm and is essentially a char array of the 26 alphabet letters which can be scrambled. The 'position' of a particle (as far as I'm aware it is simply just it's alphabet, or some numerical representation of it).
The swarm class is pretty self explanatory but includes a fitness class which scores a particle with a score between 0 and 1 (1 being the best), representing the amount of English text which the key produces.
I came across an implementation of this algorithm for (no code though) find the key to a vigenere cipher which suggests these steps:
Proposed Algorithm for finding the actual key
The PSO parameters are set in the first step. These parameters consist of number of particles (Np), the size of the key (Nd), maximum number of Iterations (Nt), Self-confidence factor (C1), Swarm confidence factor (C2), and inertia weight (w).
a) For cryptanalysis of vigenere cipher: the initial positions of the particles are determined by randomly choosing the permutations of size Nd, sampled uniformly at random from integers 0 to 25. b) Initialize velocity of each particle using:
vi = vmin+(vmax - vmin) × rand
where: vi is velocity of particle i vmax is maximum velocity, vmin is minimum velocity, rand is a random number between 0 and 1.
Calculate fitness function value for each particle
a) Decrypt the cipher text using the position of the particle as the key. b) Find the fitness function value of the text obtained in step 3 (a).
Calculate the fitness function value of each particle as discussed in step 3.
I can't seem to paste the formula into here but can be seen on page 426 here: http://www.enggjournals.com/ijcse/doc/IJCSE13-05-05-064.pdf
For anyone looking at this in the future, here is what I eventually did:
As the key for a monoalphabetic substitution cipher has to contains all 26 letters and cannot repeat, velocity is tricky to implement properly. Instead, (whether this is the best solution or not is a different story) I took 2 numbers between 0 and 1 - a swarm confidence and a self confidence - and would iterate i through each 26 letters in the array. If a random number was between 0 and the swarm confidence it would the letter at index i of the best key from the swarm. If the number was more than the swarm confidence but less than or equal to the self confidence, the same process would be repeated but with the personal best key instead. If neither of these conditions are met, the letter at index i would be kept, and then all duplicates are removed afterwards. This has yielded me some pretty good results so far.