209 lines
7.7 KiB
Python
209 lines
7.7 KiB
Python
import math
|
||
import os
|
||
import shutil
|
||
import statistics
|
||
|
||
import numpy as np
|
||
from gen import (
|
||
Chromosome,
|
||
GARunConfig,
|
||
genetic_algorithm,
|
||
initialize_random_population,
|
||
inversion_mutation_fn,
|
||
partially_mapped_crossover_fn,
|
||
)
|
||
from prettytable import PrettyTable
|
||
|
||
# В списке из 89 городов только 38 уникальных
|
||
cities = set()
|
||
with open("data.txt", "r") as file:
|
||
for line in file:
|
||
# x и y поменяны местами в визуализациях в методичке
|
||
_, y, x = line.split()
|
||
cities.add((float(x), float(y)))
|
||
cities = list(cities)
|
||
|
||
|
||
def euclidean_distance(city1, city2):
|
||
return math.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)
|
||
|
||
|
||
def build_fitness_function(cities):
|
||
def fitness_function(chromosome: Chromosome) -> float:
|
||
return sum(
|
||
euclidean_distance(cities[chromosome[i]], cities[chromosome[i + 1]])
|
||
for i in range(len(chromosome) - 1)
|
||
) + euclidean_distance(cities[chromosome[0]], cities[chromosome[-1]])
|
||
|
||
return fitness_function
|
||
|
||
|
||
# Базовая папка для экспериментов
|
||
BASE_DIR = "experiments"
|
||
|
||
# Параметры для экспериментов
|
||
POPULATION_SIZES = [10, 25, 50, 100]
|
||
PC_VALUES = [0.5, 0.6, 0.7, 0.8, 0.9] # вероятности кроссинговера
|
||
PM_VALUES = [0.2, 0.3, 0.4, 0.5, 0.8] # вероятности мутации
|
||
SAVE_AVG_BEST_FITNESS = True
|
||
|
||
# Количество запусков для усреднения результатов
|
||
NUM_RUNS = 3
|
||
|
||
# Базовые параметры (как в main.py)
|
||
BASE_CONFIG = {
|
||
"fitness_func": build_fitness_function(cities),
|
||
"max_generations": 2500,
|
||
"elitism": 2,
|
||
"cities": cities,
|
||
"initialize_population_fn": initialize_random_population,
|
||
"crossover_fn": partially_mapped_crossover_fn,
|
||
"mutation_fn": inversion_mutation_fn,
|
||
"seed": None, # None для случайности, т. к. всё усредняем
|
||
"minimize": True,
|
||
# "fitness_avg_threshold": 0.05, # критерий остановки
|
||
# "max_best_repetitions": 10,
|
||
"best_value_threshold": 7000,
|
||
# при включенном сохранении графиков на время смотреть бессмысленно
|
||
# "save_generations": [1, 50, 199],
|
||
}
|
||
|
||
|
||
def run_single_experiment(
|
||
pop_size: int, pc: float, pm: float
|
||
) -> tuple[float, float, float, float, float, float]:
|
||
"""
|
||
Запускает несколько экспериментов с заданными параметрами и усредняет результаты.
|
||
Возвращает (среднее_время_в_мс, стд_отклонение_времени, среднее_поколений,
|
||
стд_отклонение_поколений, среднее_лучшее_значение_фитнеса, стд_отклонение_лучшего_значения_фитнеса).
|
||
"""
|
||
times = []
|
||
generations = []
|
||
best_fitnesses = []
|
||
|
||
for run_num in range(NUM_RUNS):
|
||
config = GARunConfig(
|
||
**BASE_CONFIG,
|
||
pop_size=pop_size,
|
||
pc=pc,
|
||
pm=pm,
|
||
results_dir=os.path.join(
|
||
BASE_DIR,
|
||
str(pop_size),
|
||
f"pc_{pc:.3f}",
|
||
f"pm_{pm:.3f}",
|
||
f"run_{run_num}",
|
||
),
|
||
)
|
||
|
||
result = genetic_algorithm(config)
|
||
times.append(result.time_ms)
|
||
generations.append(result.generations_count)
|
||
best_fitnesses.append(result.best_generation.best_fitness)
|
||
|
||
# Вычисляем средние значения и стандартные отклонения
|
||
avg_time = statistics.mean(times)
|
||
std_time = statistics.stdev(times) if len(times) > 1 else 0.0
|
||
avg_generations = statistics.mean(generations)
|
||
std_generations = statistics.stdev(generations) if len(generations) > 1 else 0.0
|
||
avg_best_fitness = statistics.mean(best_fitnesses)
|
||
std_best_fitness = (
|
||
statistics.stdev(best_fitnesses) if len(best_fitnesses) > 1 else 0.0
|
||
)
|
||
|
||
return (
|
||
avg_time,
|
||
std_time,
|
||
avg_generations,
|
||
std_generations,
|
||
avg_best_fitness,
|
||
std_best_fitness,
|
||
)
|
||
|
||
|
||
def run_experiments_for_population(pop_size: int) -> PrettyTable:
|
||
"""
|
||
Запускает эксперименты для одного размера популяции.
|
||
Возвращает таблицу результатов.
|
||
"""
|
||
print(f"\nЗапуск экспериментов для популяции размером {pop_size}...")
|
||
print(f"Количество запусков для усреднения: {NUM_RUNS}")
|
||
|
||
# Создаем таблицу
|
||
table = PrettyTable()
|
||
table.field_names = ["Pc \\ Pm"] + [f"{pm:.3f}" for pm in PM_VALUES]
|
||
|
||
# Запускаем эксперименты для всех комбинаций Pc и Pm
|
||
for pc in PC_VALUES:
|
||
row = [f"{pc:.1f}"]
|
||
for pm in PM_VALUES:
|
||
print(f" Эксперимент: pop_size={pop_size}, Pc={pc:.1f}, Pm={pm:.3f}")
|
||
(
|
||
avg_time,
|
||
std_time,
|
||
avg_generations,
|
||
std_generations,
|
||
avg_best_fitness,
|
||
std_best_fitness,
|
||
) = run_single_experiment(pop_size, pc, pm)
|
||
|
||
# Форматируем результат: среднее_время±стд_отклонение (среднее_поколения±стд_отклонение)
|
||
# cell_value = f"{avg_time:.1f}±{std_time:.1f} ({avg_generations:.1f}±{std_generations:.1f})"
|
||
cell_value = f"{avg_time:.0f} ({avg_generations:.0f})"
|
||
|
||
if SAVE_AVG_BEST_FITNESS:
|
||
cell_value += f" {avg_best_fitness:.0f}"
|
||
|
||
if avg_generations == BASE_CONFIG["max_generations"]:
|
||
cell_value = "—"
|
||
|
||
row.append(cell_value)
|
||
table.add_row(row)
|
||
|
||
return table
|
||
|
||
|
||
def main():
|
||
"""Основная функция для запуска всех экспериментов."""
|
||
print("=" * 60)
|
||
print("ЗАПУСК ЭКСПЕРИМЕНТОВ ПО ПАРАМЕТРАМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА")
|
||
print("=" * 60)
|
||
print(f"Размеры популяции: {POPULATION_SIZES}")
|
||
print(f"Значения Pc: {PC_VALUES}")
|
||
print(f"Значения Pm: {PM_VALUES}")
|
||
print(f"Количество запусков для усреднения: {NUM_RUNS}")
|
||
print("=" * 60)
|
||
|
||
# Создаем базовую папку
|
||
if os.path.exists(BASE_DIR):
|
||
shutil.rmtree(BASE_DIR)
|
||
os.makedirs(BASE_DIR)
|
||
|
||
# Запускаем эксперименты для каждого размера популяции
|
||
for pop_size in POPULATION_SIZES:
|
||
table = run_experiments_for_population(pop_size)
|
||
|
||
print(f"\n{'='*60}")
|
||
print(f"РЕЗУЛЬТАТЫ ДЛЯ ПОПУЛЯЦИИ РАЗМЕРОМ {pop_size}")
|
||
print(f"{'='*60}")
|
||
print(
|
||
f"Формат: среднее_время±стд_отклонение_мс (среднее_поколения±стд_отклонение)"
|
||
)
|
||
print(f"Усреднено по {NUM_RUNS} запускам")
|
||
print(table)
|
||
|
||
pop_exp_dir = os.path.join(BASE_DIR, str(pop_size))
|
||
os.makedirs(pop_exp_dir, exist_ok=True)
|
||
with open(os.path.join(pop_exp_dir, "results.csv"), "w", encoding="utf-8") as f:
|
||
f.write(table.get_csv_string())
|
||
print(f"Результаты сохранены в папке: {pop_exp_dir}")
|
||
|
||
print(f"\n{'='*60}")
|
||
print("ВСЕ ЭКСПЕРИМЕНТЫ ЗАВЕРШЕНЫ!")
|
||
print(f"Результаты сохранены в {BASE_DIR}")
|
||
print(f"{'='*60}")
|
||
|
||
|
||
if __name__ == "__main__":
|
||
main()
|