Skip to content

Instantly share code, notes, and snippets.

@celaus
Created August 25, 2018 21:19
Show Gist options
  • Save celaus/d5a55e723ce233f2b83af36a4cf456b4 to your computer and use it in GitHub Desktop.
Save celaus/d5a55e723ce233f2b83af36a4cf456b4 to your computer and use it in GitHub Desktop.
PMX - Partially Mapped Crossover
function x(s, t) {
let _map1 = {};
let _map2 = {};
const x1 = Math.floor(Math.random() * (s.length - 1));
const x2 = x1 + Math.floor(Math.random() * (s.length - x1));
let offspring = [Array.from(s), Array.from(t)];
for (let i = x1; i < x2; i++) {
offspring[0][i] = t[i];
_map1[t[i]] = s[i];
offspring[1][i] = s[i];
_map2[s[i]] = t[i];
}
for (let i = 0; i < x1; i++) {
while (offspring[0][i] in _map1) {
offspring[0][i] = _map1[offspring[0][i]];
}
while (offspring[1][i] in _map2) {
offspring[1][i] = _map2[offspring[1][i]];
}
}
for (let i = x2; i < s.length; i++) {
while (offspring[0][i] in _map1) {
offspring[0][i] = _map1[offspring[0][i]];
}
while (offspring[1][i] in _map2) {
offspring[1][i] = _map2[offspring[1][i]];
}
}
return offspring;
}
function PMXCrossover(pop) {
const p = pop.members;
const rounds = p.length % 2 ? p.length - 1 : p.length;
for (let i = 1; i < rounds; i += 2) {
const s = p[i].genome;
const t = p[i - 1].genome;
x(s, t).forEach((offspring) => {
if (new Set(offspring).size != _cities.length) {
console.log(offspring);
throw new Error("nope");
}
pop.members.push(new Citizen(offspring));
});
}
}
fn crossover(&self, other: &TspTour) -> TspTour {
// PMX crossover
let s = &self.tour;
let t = &other.tour;
let mut rng = self.rng_cell.borrow_mut();
let x1 = rng.gen_range(0, s.len() - 1);
let x2 = rng.gen_range(x1, s.len());
let mut offspring = vec![0; s.len()];
let mut mapping: Vec<Option<usize>> = vec![None; s.len()];
for i in x1..x2 {
offspring[i] = t[i];
mapping[t[i]] = Some(s[i]);
}
for i in 0..x1 {
let mut o = mapping[s[i]];
let mut last = None;
while o.is_some() {
last = o;
o = mapping[o.unwrap()];
}
offspring[i] = if let Some(v) = last { v } else { s[i] };
}
for i in x2..s.len() {
let mut o = mapping[s[i]];
let mut last = None;
while o.is_some() {
last = o;
o = mapping[o.unwrap()];
}
offspring[i] = if let Some(v) = last { v } else { s[i] };
}
TspTour {
tour: offspring,
cities: self.cities.clone(),
rng_cell: self.rng_cell.clone(),
}
}
@matiasmicheletto
Copy link

Hi, thanks for sharing this gist, I actually included your code in my project: https://github.com/matiasmicheletto/dna-solver.
Cheers!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment