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
- Initialization of PSO search algorithm parameters
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).
- Initialization of discrete birds or population
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.
- List item
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).
- Update velocity and position of the particles
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