Struktura programu a specifikace
Než začneme programovat, měli byste si předem rozmyslet, jaká bude struktura programu.- Objektová hierarchie
- Jaké budou třídy nebo struktury a jaké v nich budou proměnné?
- Application Programming Interface
- Jaké způsobem se budou třídy používat, tj. jakými funkcemi budou jednotlivé třídy dostávat potřebná data ke své činnosti a jaké informace budou poskytovat zbytku programu?
- Běhový model
- Kdy se budou jednotlivé funkce volat mezi sebou?
Třída instance a řešení
Při řešení libovolné optimalizační úlohy začneme se dvěma třídami.- Třída instanci problému
- Obsahuje všechna vstupní data našeho problému, která již máme popsána v popisu problému. Obsah této třídy je načten na při spuštění programu a v průběhu výpočtu se nic nemění.
- Třída jednoho řešení
- Obsahuje všechna data jednoznačně popisující jedno řešení našeho problému. Jak vypadá řešení též máme popsáno v popisu problému. Dále se může hodit do této třídy uložit další informace, které bychom jinak museli opakovaně počítat. Zejména se určitě hodí uložit si hodnotu cílové funkce nebo fitness.
Statická a dynamická data
Představme si, že chceme optimalizovat sofistikovaný výtahový systém, ve kterém máme různé typy výtahů (šachet) s různými parametry (rychlost, kapacita, atd.). Pro každou šachtu máme tedy statická data obsahující její parametry a při simulaci máme ještě dynamická data (aktuální pozice a seznam pasažérů). V tomto případě je vhodné data pro šachtu rozdělit do dvou tříd. Jedna třída obsahuje vstupní statické parametry a druhá třída obsahuje dynamické informace. Jelikož ve výtahovém systému máme několik šachet, tak si je uložíme do pole. Třída instance problému obsahuje pole statických parametrů a řešení (nebo samostatná třída pro simulaci) obsahuje pole dynamických dat.Různé algoritmy pro řešení problému
V rámci práce chceme vyzkoušet různé algoritmy k řešení našeho problému. Jeden algoritmus můžeme mít různé varianty (například v genetickém algoritmu můžeme testovat různé metody křížení) a mít různé hyperparametry (například pravděpodobnost mutace). Tyto algoritmy se navíc můžou používat navzájem (například můžeme samostatně testovat genetický algoritmus a lokální prohledávání a pak je spojit do memetického). Jak se v takovém programu neztratit? Vytvoříme si třídy, které budou obsahovat jednotlivé algoritmy. Tyto třídy budou obsahovat pouze hyperparametry daného algoritmu a nikoliv instance problému a řešení, které budou dostávat funkce těchto tříd pomocí argumentů.Vytváření počátečního řešení
Řada algoritmů začíná z jednoho nebo více řešení, které postupně zlepšuje. Počáteční řešení je možné vytvářet různými způsoby, a proto budeme mít pro každou metodu jednu třídu. Ve většině jazyků se hodí tyto třídy odvodit od společného předka, abychom mohli používat virtuální funkce.
class SolutionGenerator:
virtual function generate(problem_instance) // Returns one created solution for a given problem instance
class RandomSolutionGenerator(inherited from SolutionGenerator):
override function generate(problem_instance)
class GreedySolutionGenerator(inherited from SolutionGenerator):
variable smartness // A hyperparameter for the greedy algorithm
constructor(smartness) // Create instance of the class GreedySolutionGenerator and set the smartness
override function generate(problem_instance)
Fitness
Náš problém má nejspíš jednu cílovou funkci, takže se zdá, že by nám měla stačit jedna funkce, která pro dané řešení spočítá fitness. Ale často se též hodí použít virtuální funkce, i když nemáme problém vícekriteriální optimalizace. Například nám náhodný generátor nebo evoluce vytváří nepřípustná řešení, kde porušení podmínek chceme ve fitness penalizovat vhodnými váhami.
class Fitness:
virtual function calculate_fitness(problem_instance, problem_solution)
class FitnessPenalty(inherited from Fitness):
variable weight
constructor(weight)
override function calculate_fitness(problem_instance, problem_solution)
Genetické algoritmy
Nyní uvažujme genetický algoritmus, ve kterém chceme mít různé varianty inicializace populace, selekce, křížení, mutací s nastavením hyperparametrů. Začneme mutací.
class Mutation:
virtual function mutate(problem_instance, problem_solution) // Returns mutated solution
class FlipMutation(inherited from Mutation): // Change every bit with a given probability
variable probability_mutation
constructor(probability_mutation)
override function mutate(problem_instance, problem_solution)
class SwapMutation(inherited from Mutation): // Choose two passangers assigned to different cars and swap them
variable number_of_swaps
constructor(number_of_swaps)
override function mutate(problem_instance, problem_solution)
Křížení je analogické, jen virtuální funkce dostává dvě řešení. Selekce dostane celou populaci a vrací vybraného jedince.
Možná se ptáte, zda všechny funkce musí dostávat instanci problému. Fitness určitě potřebuje znát instanci, protože musí zjistit, zda jsou splněny všechny požadavky zadání. Selekce by neměla záviset na konkrétní instanci (dokonce by měla být obecná pro libovolný problém). U mutace a křížení nemusí být odpověď jednoznačná a může záviset na daném problému.
Jednotlivé operátory zapouzdříme do třídy genetického algoritmu. Opět můžeme mít více tříd pro různé varianty.
class GeneticAlgorithm:
virtual function run_genetic_algorithm(problem_instance)
class GeneticAlgorithmWithElitism:
variables generator, fitness, crossover, mutation, population_size, generations
constructor(generator, fitness, crossover, mutation, population_size, generations)
virtual function run_genetic_algorithm(problem_instance)
Poskládání algoritmu a spuštění experimentů
Celý algoritmus nyní můžeme poskládat dohromady a spustit.
algorithm = GeneticAlgorithm(
generator = RandomSolutionGenerator(),
fitness = FitnessPenalty(weight = 1000),
crossover = MultiPointCrossover(points = 3),
mutation = FlipMutation(probability_mutation = 0.001),
population_size = 100,
generations = 1000
)
instance = load_instance("../datasets/my_fancy_graph.json")
algorithm.run_genetic_algorithm(instance)
Tento postup se bude hodit pro odladění jednotlivých částí programů.
Poté budeme chtít spustit program na celém datasetu a vyzkoušet různé operátory s různými parametry.
Vytvoříme si tedy pole instancí a algoritmů.
generators = [
RandomSolutionGenerator(),
GreedySolutionGenerator(smartness = s) for s in [ 1, 10, 100 ]
]
fitness = FitnessPenalty(1000)
crossovers = [
MultiPointCrossover(points = p) for p in [ 1, 2, 3, 5, 10 ]
]
mutations = [
FlipMutation(probability_mutation = p) for p in [ 0.000001, 0.00001, 0.0001, 0.001, 0.01, 0.1 ],
SwapMutation(number_of_swaps = n) for p in [ 1, 2, 3, 5, 10 ]
]
population_sizes = 10:10:100,
generations = 1000 // We can store progress after every generation
algorithms = [
GeneticAlgorithm(
generator = generator,
fitness = fitness,
crossover = crossover,
mutation = mutations,
population_size = population_size,
generations = generations
)
for generator in generators
for crossover in crossovers
for mutation in mutations
for population_size in population_sizes
]
instances = [ load_instance(filename) for filename in get_files_in_directory("../datasets/") ]
for algorithm in algorithms:
for instance in instances:
result = algorithm.run_genetic_algorithm(instance)
save_result(result = result, filename = algorithm.description())
Nyní se můžeme věnovat jiným činnostem, protože tento program poběží hodně dlouhou dobu bez naší asistence.
Až tento program skončí, tak spustíme skript, který načte všechny výsledky a vytvoří grafy a tabulky do závěrečné práce.
Oddělení algoritmu a instance problému
Z uvedeného příkladu nemusí být zjevné, proč jsme oddělili třídy algoritmu a instance. Pokud v celém běhu programu máme jen jednu instanci problému, tak bychom ji mohli uložit kamkoliv i do globálních proměnných, i když by to nebyl moc pěkný softwarový návrh. Výhoda tohoto přístupu začne být zjevná v situaci, kdy řešení problému je rozděleno na řešení několika podproblémů.
Například v branch-and_price je hlavní smyčka algoritmu založená na branch-and-cut, která postupně vytváří jednotlivé větve.
Každá větev dostane k jednu relaxovanou úlohu, kterou můžeme vyřešit pomocí column generation, který musí opakovaně řešit různé subúlohy.
Algoritmus můžeme poskládat podobně jako u evoluce.
algorithm = BranchAndPrice(
relax_solver = ColumnGenerator(
subproblem_solver = DynamicProgramming()
)
)
Branch-and-bound vytváří instance relaxovaného úloh, které předává column generation, který vytváří instance subproblému a předáváje dynamickému programování.
Opět tento koncept můžeme rozšířit o generátory řezných nadrovin, hledání heuristických řešení, či subgradientními metodami k řešení master problému.
Lokální prohledávání
Popsali jsme, jak algoritmus zapouzdřit do objektu, které mu je možné předávát nejen hyperparametry, ale i další algoritmy na řešení subúloh. Tento koncept je možné použív v algoritmech lokálního prohledávání k vytvoření naprosto modulárního programu. Základní myšlenka algoritmů lokálního prohledávání je, že dostanou libovolné řešení, které se malými změnami snaží zlepšit. Proto všechny třídy budou mít virtuální funkci search, která pro dané řešení vrátí jiné.
class LocalSearch:
virtual function search(problem_instance, problem_solution)
Vytvoříme sadu operátorů (například 2-OPT).
class Operator2OPT(inherited from LocalSearch):
override function search(problem_instance, problem_solution)
V jednom algoritmu lokálního prohledávání obvykle uvažujeme množinu operátorů, takže vytvoříme třídu zajišťující volání všech operátorů dané množiny.
class OperatorList(inherited from LocalSearch):
variable operators // A list of instances of classes inherited from LocalSearch
constructor(operators)
override function search(problem_instance, problem_solution)
V praxi se daný operátor spouští několikrát, tak si můžeme vytvořit třídu obsahující operátor a hyperparametr obsahujicí počet volání.
Takto můžeme neomezeně vytvářet kombinace operátorů, které můžeme použít například v simulovaném žíhání.
class SimulatedAnnealing(inherited from LocalSearch):
variable operator, initial_temperature
constructor(operator, initial_temperature)
override function search(problem_instance, problem_solution)
algorithm = SimulatedAnnealing(
operator = OperatorList(
Operator2OPT(),
OperatorSwap()
)
initial_temperature = 42
)
Podobně můžeme postupovat v dalších algoritmech.
- Gradientní metoda
- Funkce search místo malých změn bude počítat gradienty.
- Tabu search
- Řekne, zda jste v daném řešení už byli.
- Memetický algoritmus
- Třída genetického algoritmu rozšířená o proměnnou obsahující lokální prohledávání
- Iterované lokální prohledávání
- Třída dostane dva operátory, kde první slouží k nalezení lokálního minima a druhý k perturbaci.
Paralelní programování
Dnešní procesory obsahují velké množství jader a je přirozené pokusit se zrychlit experimenty paralelním programováním. V řadě evolučních algoritmů je možné počítat fitness paralalelně pro několik řešení najednou. Pokud správně implementujeme výše uvedený postup, tak se ani nebudeme muset moc starat o zámky, protože funkce fitness dostává instanci problému, kterou pouze čte, a řešení, ke kterému přistupuje jen jedno vlákno. Stačí mít jedno hlavní vlákno, které se stará o evoluci a sype řešení do channel, ze kterého si je pomocná vlákna po jednom berou k výpočtu fitness.
Pokud nás neláká možnost vyzkoušet si paralelní programování (nebo používáme Python), můžeme nechat program jednovláknový a všechna jádra použít při paralelním spouštění více experimentů najednou.
Nejprve si do našeho programu připíšeme funkci, která z argumentů příkazové řádky vytvoří zadaný algoritmus a spustí jej na zadanou instanci.
Poté napíšeme jednoduchý skript experiments, který vypíše argumenty všech experimentů.
for generator in generators:
for crossover in crossovers:
for mutation in mutations:
for population_size in population_sizes:
for instance in get_files_in_directory("../datasets/"):
print("-g $generator -c $crossover -m $mutation -s $population_size -i $instance")
Všechny experimenty budeme spouštět postupně s použitím příkazu xargs, který zajistí, že najednou poběží zadaný počet experimentů.
./experiments | xargs -I CMD --max-procs=3 ./my_single_experiment CMD