| |
- HighOrderChem.HighOrderChem
-
- MolecularTSP
- Point
- TSPgraph
class MolecularTSP(HighOrderChem.HighOrderChem) |
| |
Methods defined here:
- __init__(self, nc, ring=True)
- initialize molecular TSP with a graph of cities and a reactor
with random candidate tours and rules that operate on tours;
the graph contains 'nc' cities forming a ring (when ring=True),
or scattered randomly (when ring=False)
- bestMolecule(self)
- returns the best molecule in the data multiset
- cutMachine(self, mol)
- C-Machine: transposes the segment lying between two cities
behind a third city
e.g. 1 2 3 4 5 6 7 ==> 1 4 5 2 3 6 7
^ ^ | x |^ ^
- cutOrInvertOperator(self, tour, invert=False)
- implements the C-Machine operator when invert=False
implements the I-Machine operator when invert=True
- exchangeMachine(self, mol)
- E-Machine implementation:
invokes the E-Machine operator, evaluates the fitness of
the new molecule, compares it with the original one, and
returns the fittest molecule
- exchangeOperator(self, tour)
- E-Machine operator:
chooses two random cities in a tour and inverts their order
e.g. 1 2 3 4 5 6 7 ==> 1 2 3 6 5 4 7
^ ^ ^ ^
- fitness(self, tour)
- calculate the fitness of a tour
- fitter(self, fit1, fit2)
- true if the fitness value fit1 is better than value fit2
- invertMachine(self, mol)
- I-Machine: same as the C-Machine but the segment cut is
reversed before insertion
e.g. 1 2 3 4 5 6 7 ==> 1 4 5 3 2 6 7
^ ^ | x |^ ^
- newMolecule(self, fit, tour)
- constructs a molecule with syntax:
fitness [ city1, city2, ... ]
- parseMolecule(self, mol)
- parses the molecule, returning its fitness and tour components
- randomMolecule(self)
- create a random candidate molecule (fit, c1, c2, ...)
- randomPair(self, tour)
- returns a random pair of positions within a tour
- recombinationMachine(self, mol1, mol2)
- R-Machine: recombines 2 tours and selects the 2 fitter tours
out of the multiset of 4 tours formed by the 2 parents plus the
2 generated offsprings
- recombinationOperator(self, tour1, tour2)
- R-Machine operator: recombines two tours
example:
[1 2 3 4 5 6 7], [3 6 1 4 5 2 7] ==>
^ |-----|
[1 4 5 2 2 3 4 5 6 7] ==> [1 4 5 2 3 6 7]
|-----|
- run(self)
- run the Molecular TSP algorithm for up to a maximum number of
generations, or until a sufficiently optimal solution is
found;
produces a set of output files, one for each individual
in the initial population, and one for each individual in
the final population
- splitTour(self, tour, p1, p2)
- splits the tour in two segments:
1. the segment starting at position p1, until position p2-1
2. the segment starting at position p2, until position p1-1
in a circular way, for example:
1 2 3 4 5 6 7 ==> [2 3], [4 5 6 7 1]
^ ^
p1 p2
1 2 3 4 5 6 7 ==> [4 5 6 7 1], [2, 3]
^ ^
p2 p1
if the positions p1 and p2 coincide, the first segment is
equal to the tour, and the second segment is empty
- traceAll(self, gen)
- print all molecules in the data multiset
Methods inherited from HighOrderChem.HighOrderChem:
- is_effective(self, educts, products)
- true if the reaction defined by educts --> products is
effective, that is the product multiset is different from the
educt multiset
- isrule(self, mol)
- true if molecule 'mol' contains a reaction rule of the form
function(args), where function is a python function call
and args are the parameters for the function
- iterate(self)
- run one iteration of high-order algorithm: pick a random
reaction rule, fill its binding sites with as many molecules
as needed, and fire it.
returns a triple (r, e, p) where r is the rule that has
been fired, 'e' is the educt list and 'p' is the product
list
|
class TSPgraph |
| |
Methods defined here:
- __init__(self, nc, ring=True)
- create a random map containing 'nc' cities;
if the 'ring' flag is set, puts all the cities around a ring;
else scatters them randomly on a 2D surface
- buildFullMesh(self)
- fully-meshed graph with roads from all cities to all others
- cityDistance(self, city1, city2)
- Euclidean distance between two cities
- createRingTopo(self)
- ring topology: cities are placed on a ring with radius
proportional to the total number of cities
- createRndTopo(self)
- random topology: cities placed at random coordinates
- distance(self, p1, p2)
- Euclidean distance between two points
- occupied(self, x, y)
- true if point (x,y) is too close to another city
- randomTour(self, ns)
- walk ns steps randomly on the graph, without going back to the
same city; returns the tour generated
- trace(self)
- print city number and coordinates for plotting
- traceTour(self, tour, fname)
- prints tour for plotting
| |