Assets/Scripts/OptimizationLogic/Core/GeneticAlgorithm.cs - master - GeekNerd/ServerModelingProject

Assets/Scripts/OptimizationLogic/Core/GeneticAlgorithm.cs
507 строк20 KB
Gorney-Alex
Init
30 май 2026, 19:05
30 май 2026, 19:053cdcc49
using System;
using System.Collections.Generic;
using System.Threading;
using System.Threading.Tasks;
using DataClasses;
using DataClasses.Algorithm;
using UnityEngine;

namespace OptimizationLogic.Core
{
    public sealed class GeneticAlgorithm
    {
        private readonly PlacementValidator _placementValidator = new();
        private readonly ZonalThermalModel _thermalModel = new();
        private readonly AisleValidator _aisleValidator = new();
        private readonly TopologyValidator _topologyValidator = new();

        private static readonly float[] Rotations = { 0f, 90f, 180f, 270f };

        public Task<Chromosome> OptimizeAsync(
            RoomConfig room,
            IReadOnlyList<PlacementZone> zones,
            IReadOnlyList<RackData> models,
            GaSettings settings,
            IProgress<GaProgress> progress,
            CancellationToken ct)
        {
            return Task.Run(() => Optimize(room, zones, models, settings, progress, ct), ct);
        }

        public Chromosome Optimize(
            RoomConfig room,
            IReadOnlyList<PlacementZone> zones,
            IReadOnlyList<RackData> models,
            GaSettings settings,
            IProgress<GaProgress> progress,
            CancellationToken ct)
        {
            if (room == null) throw new ArgumentNullException(nameof(room));
            if (zones == null) throw new ArgumentNullException(nameof(zones));
            if (models == null) throw new ArgumentNullException(nameof(models));
            settings ??= new GaSettings();

            int popSize = Mathf.Max(2, settings.PopulationSize > 0 ? settings.PopulationSize : 100);
            int generations = Mathf.Max(1, settings.Generations > 0 ? settings.Generations : 120);
            int earlyStop = Mathf.Max(0, settings.EarlyStopGenerations);
            int elite = Mathf.Max(1, settings.EliteCount > 0 ? settings.EliteCount : 1);
            int tournament = Mathf.Max(2, settings.TournamentSize);
            float crossoverRate = settings.CrossoverRate > 0f ? settings.CrossoverRate : 0.8f;
            float mutationRate = settings.MutationRate > 0f ? settings.MutationRate : 0.15f;
            float initMutProb = settings.InitMutationProb > 0f ? settings.InitMutationProb : 0.35f;

            NormalizeWeights(settings, out float w1, out float w2, out float w3, out float w4);

            Debug.Log($"[GA] weights: w1(placed)={w1:F3} w2(thermal)={w2:F3} w3(aisle)={w3:F3} w4(topology)={w4:F3}");
            Debug.Log($"[GA] settings: pop={popSize} gen={generations} cross={crossoverRate} mut={mutationRate}");

            System.Random rng = new System.Random(settings.RandomSeed);

            // Initial population
            GreedyPlacer greedy = new GreedyPlacer();
            Chromosome baseChrom = greedy.Place(room, zones, models);
            baseChrom.Fitness = CalculateFitness(baseChrom, room, zones, models, w1, w2, w3, w4);

            Debug.Log($"[GA] greedy fitness={baseChrom.Fitness:F4}, placed={baseChrom.PlacedCount}/{baseChrom.Genes.Count}");

            List<Chromosome> pop = new List<Chromosome>(popSize);
            pop.Add(CloneChromosome(baseChrom));

            for (int i = 1; i < popSize; i++)
            {
                Chromosome c = CloneChromosome(baseChrom);
                InitMutateChromosome(c, zones, room, rng, initMutProb);
                RepairChromosome(c, room, models, zones);
                c.Fitness = CalculateFitness(c, room, zones, models, w1, w2, w3, w4);
                pop.Add(c);
            }

            Chromosome best = CloneChromosome(pop[0]);
            float bestFitness = best.Fitness;
            int noImprove = 0;

            for (int gen = 0; gen < generations; gen++)
            {
                if (ct.IsCancellationRequested) break;

                pop.Sort((a, b) => b.Fitness.CompareTo(a.Fitness));
                if (pop[0].Fitness > bestFitness)
                {
                    bestFitness = pop[0].Fitness;
                    best = CloneChromosome(pop[0]);
                    noImprove = 0;
                }
                else
                {
                    noImprove++;
                }

                // Report progress every 5 generations
                if (gen % 5 == 0)
                {
                    var temps = _thermalModel.ComputeZoneTemperatures(room, zones, best.Genes, models);
                    float ri = _topologyValidator.ComputeRecirculationIndex(best.Genes, zones);
                    progress?.Report(new GaProgress(gen, generations, bestFitness, _thermalModel.MaxTemperature, ri));
                }

                if (earlyStop > 0 && noImprove >= earlyStop)
                    break;

                List<Chromosome> next = new List<Chromosome>(popSize);

                // Elitism
                for (int e = 0; e < elite && e < pop.Count; e++)
                    next.Add(CloneChromosome(pop[e]));

                while (next.Count < popSize)
                {
                    Chromosome p1 = TournamentSelect(pop, tournament, rng);
                    Chromosome p2 = TournamentSelect(pop, tournament, rng);

                    Chromosome child;
                    if (rng.NextDouble() < crossoverRate)
                        child = Crossover(p1, p2, rng);
                    else
                        child = CloneChromosome(p1);

                    MutateChromosome(child, zones, room, rng, mutationRate);

                    // TZ: if invalid genes occur, mark them as not placed (repair)
                    RepairChromosome(child, room, models, zones);

                    child.Fitness = CalculateFitness(child, room, zones, models, w1, w2, w3, w4);
                    next.Add(child);
                }

                pop = next;
            }

            Debug.Log($"[GA] RESULT fitness={best.Fitness:F4}, placed={best.PlacedCount}");

            // Manual RI check for logging
            int totalPlaced = 0;
            int wrongOriented = 0;
            for (int i = 0; i < best.Genes.Count; i++)
            {
                RackGene g = best.Genes[i];
                if (!g.IsPlaced) continue;
                totalPlaced++;

                Vector2 front = Geometry2D.FrontVectorFromRotation(g.Rotation);

                PlacementZone zone = null;
                for (int z = 0; z < zones.Count; z++)
                {
                    if (zones[z].ZoneId == g.ZoneId) { zone = zones[z]; break; }
                }

                if (zone != null && Vector2.Dot(front, zone.ColdAirDirection) >= 0f)
                    wrongOriented++;

                Debug.Log($"  Result Gene[{i}] pos=({g.PositionX:F2},{g.PositionZ:F2}) rot={g.Rotation} zone={g.ZoneId} placed={g.IsPlaced}");
            }
            Debug.Log($"[GA] RI check: {wrongOriented}/{totalPlaced} wrong oriented");

            return best;
        }

        public float CalculateFitness(Chromosome c, RoomConfig room, IReadOnlyList<PlacementZone> zones, IReadOnlyList<RackData> models)
        {
            NormalizeWeights(null, out float w1, out float w2, out float w3, out float w4);
            return CalculateFitness(c, room, zones, models, w1, w2, w3, w4);
        }

        private float CalculateFitness(Chromosome c, RoomConfig room, IReadOnlyList<PlacementZone> zones, IReadOnlyList<RackData> models,
            float w1, float w2, float w3, float w4)
        {
            if (c == null || c.Genes == null) return 0f;

            // Step 1: full validity check — any violation => 0
            List<RackGene> placed = new();
            for (int i = 0; i < c.Genes.Count; i++)
            {
                RackGene g = c.Genes[i];
                if (!g.IsPlaced) continue;

                if (!_placementValidator.IsPlacementValid(room, placed, g, models))
                    return 0f;

                placed.Add(g);
            }

            int n = c.Genes.Count;
            int placedCount = placed.Count;

            float fplaced = n == 0 ? 0f : (float)placedCount / n;

            // Thermal fitness
            var temps = _thermalModel.ComputeZoneTemperatures(room, zones, c.Genes, models);
            float penaltyT = _thermalModel.ComputeThermalPenalty(room, temps);
            float fthermal = 1f / (1f + penaltyT);

            // Aisle fitness
            float faisle = 0f;
            if (placedCount > 0)
            {
                HashSet<int> acc = _aisleValidator.ComputeAccessibleRacks(room, c.Genes, models);
                faisle = (float)acc.Count / placedCount;
            }

            // Topology fitness
            float ftopology = _topologyValidator.ComputeTopologyFitness(c.Genes, zones);

            float f = w1 * fplaced + w2 * fthermal + w3 * faisle + w4 * ftopology;
            return Mathf.Clamp01(f);
        }

        private static void NormalizeWeights(GaSettings settings, out float w1, out float w2, out float w3, out float w4)
        {
            if (settings == null)
            {
                w1 = 0.30f; w2 = 0.25f; w3 = 0.15f; w4 = 0.30f;
                return;
            }

            w1 = settings.WeightPlacement;
            w2 = settings.WeightThermal;
            w3 = settings.WeightAisle;
            w4 = settings.WeightTopology;

            float sum = w1 + w2 + w3 + w4;
            if (sum <= 1e-6f)
            {
                w1 = 0.30f; w2 = 0.25f; w3 = 0.15f; w4 = 0.30f;
                return;
            }

            w1 /= sum; w2 /= sum; w3 /= sum; w4 /= sum;
        }

        private static Chromosome TournamentSelect(List<Chromosome> pop, int tournamentSize, System.Random rng)
        {
            Chromosome best = null;
            for (int i = 0; i < tournamentSize; i++)
            {
                Chromosome c = pop[rng.Next(pop.Count)];
                if (best == null || c.Fitness > best.Fitness)
                    best = c;
            }
            return best;
        }

        private static Chromosome Crossover(Chromosome a, Chromosome b, System.Random rng)
        {
            Chromosome child = new Chromosome();
            int n = Mathf.Min(a.Genes.Count, b.Genes.Count);
            if (n == 0) return child;

            int t = rng.Next(1, n);
            for (int i = 0; i < n; i++)
            {
                child.Genes.Add(i < t ? CloneGene(a.Genes[i]) : CloneGene(b.Genes[i]));
            }
            return child;
        }

        private static void InitMutateChromosome(Chromosome c, IReadOnlyList<PlacementZone> zones, RoomConfig room, System.Random rng, float initMutationProb)
        {
            if (c?.Genes == null || zones == null) return;

            // TZ: initial population = copies of greedy with independent per-gene mutation:
            // random GridIndex (here: candidate position) in same zone + random rotation.
            for (int i = 0; i < c.Genes.Count; i++)
            {
                if (rng.NextDouble() >= initMutationProb) continue;
                RackGene g = c.Genes[i];

                PlacementZone z = FindZone(zones, g.ZoneId);
                if (z != null && z.CandidatePositions.Count > 0)
                {
                    Vector2 p = z.CandidatePositions[rng.Next(z.CandidatePositions.Count)];
                    g.PositionX = p.x;
                    g.PositionZ = p.y;
                }
                g.Rotation = Rotations[rng.Next(Rotations.Length)];
                c.Genes[i] = g;
            }
        }

        private static void MutateChromosome(Chromosome c, IReadOnlyList<PlacementZone> zones, RoomConfig room, System.Random rng, float mutationRate)
        {
            if (c?.Genes == null || zones == null || room == null) return;

            float step = room.GridStep > 0f ? room.GridStep : 0.6f;

            for (int i = 0; i < c.Genes.Count; i++)
            {
                RackGene g = c.Genes[i];

                // TZ: 4 mutation types applied independently
                if (rng.NextDouble() < mutationRate)
                {
                    // Shift: try to move by 1 grid step within the same zone
                    PlacementZone z = FindZone(zones, g.ZoneId);
                    if (z != null && z.CandidatePositions.Count > 0)
                    {
                        Vector2 delta = rng.Next(2) == 0 ? Vector2.right : Vector2.up;
                        if (rng.Next(2) == 0) delta = -delta;
                        Vector2 target = new Vector2(g.PositionX, g.PositionZ) + delta * step;

                        if (TrySnapToNearbyCandidate(z.CandidatePositions, target, step * 0.51f, out Vector2 snapped))
                        {
                            g.PositionX = snapped.x;
                            g.PositionZ = snapped.y;
                        }
                    }
                }

                if (rng.NextDouble() < mutationRate)
                {
                    // Rotate
                    g.Rotation = Rotations[rng.Next(Rotations.Length)];
                }

                if (rng.NextDouble() < mutationRate)
                {
                    // Relocate
                    PlacementZone z = FindZone(zones, g.ZoneId);
                    if (z != null && z.CandidatePositions.Count > 0)
                    {
                        Vector2 p = z.CandidatePositions[rng.Next(z.CandidatePositions.Count)];
                        g.PositionX = p.x;
                        g.PositionZ = p.y;
                    }
                }

                if (rng.NextDouble() < mutationRate)
                {
                    // Toggle
                    if (g.IsPlaced)
                    {
                        g.IsPlaced = false;
                    }
                    else
                    {
                        if (g.ZoneId < 0)
                        {
                            // Zone is unknown -> keep unplaced
                            c.Genes[i] = g;
                            continue;
                        }

                        // Enable only if the zone exists and has candidates (prevents ZoneId = -1)
                        PlacementZone z = FindZone(zones, g.ZoneId);
                        if (z != null && z.CandidatePositions.Count > 0)
                        {
                            Vector2 p = z.CandidatePositions[rng.Next(z.CandidatePositions.Count)];
                            g.PositionX = p.x;
                            g.PositionZ = p.y;
                            g.IsPlaced = true;
                        }
                    }
                }

                c.Genes[i] = g;
            }
        }

        private static bool TrySnapToNearbyCandidate(IReadOnlyList<Vector2> candidates, Vector2 target, float maxDist, out Vector2 snapped)
        {
            float best = maxDist;
            snapped = default;
            for (int i = 0; i < candidates.Count; i++)
            {
                Vector2 p = candidates[i];
                float d = Vector2.Distance(p, target);
                if (d <= best)
                {
                    best = d;
                    snapped = p;
                }
            }
            return best <= maxDist;
        }

        private void RepairChromosome(Chromosome c, RoomConfig room, IReadOnlyList<RackData> models, IReadOnlyList<PlacementZone> zones)
        {
            if (c?.Genes == null) return;

            List<RackGene> placed = new();
            int placedCount = 0;

            for (int i = 0; i < c.Genes.Count; i++)
            {
                RackGene g = c.Genes[i];
                if (!g.IsPlaced)
                {
                    c.Genes[i] = g;
                    continue;
                }

                if (_placementValidator.IsPlacementValid(room, placed, g, models))
                {
                    placed.Add(g);
                    placedCount++;
                    c.Genes[i] = g;
                }
                else
                {
                    bool repaired = false;

                    PlacementZone zone = FindZone(zones, g.ZoneId);
                    if (zone != null && zone.CandidatePositions != null && zone.CandidatePositions.Count > 0)
                    {
                        Vector2 coldDir = zone.ColdAirDirection;
                        float[] sortedRots = SortRotationsByColdDir(Rotations, coldDir);

                        int count = zone.CandidatePositions.Count;
                        int tryCount = Mathf.Min(30, count);
                        int start = (i * 7919) % count;
                        int step = Mathf.Max(1, count / Mathf.Max(1, tryCount));

                        for (int p = 0; p < tryCount && !repaired; p++)
                        {
                            Vector2 pos = zone.CandidatePositions[(start + p * step) % count];

                            for (int r = 0; r < sortedRots.Length && !repaired; r++)
                            {
                                RackGene candidate = new RackGene
                                {
                                    ModelIndex = g.ModelIndex,
                                    IsPlaced = true,
                                    Rotation = sortedRots[r],
                                    PositionX = pos.x,
                                    PositionZ = pos.y,
                                    ZoneId = g.ZoneId
                                };

                                if (_placementValidator.IsPlacementValid(room, placed, candidate, models))
                                {
                                    placed.Add(candidate);
                                    placedCount++;
                                    c.Genes[i] = candidate;
                                    repaired = true;
                                }
                            }
                        }
                    }

                    if (!repaired)
                    {
                        g.IsPlaced = false;
                        c.Genes[i] = g;
                    }
                }
            }

            c.PlacedCount = placedCount;
        }

        private static float[] SortRotationsByColdDir(float[] rotations, Vector2 coldDir)
        {
            float[] sorted = (float[])rotations.Clone();
            Array.Sort(sorted, (a, b) =>
            {
                float dotA = Vector2.Dot(Geometry2D.FrontVectorFromRotation(a), coldDir);
                float dotB = Vector2.Dot(Geometry2D.FrontVectorFromRotation(b), coldDir);
                return dotA.CompareTo(dotB);
            });
            return sorted;
        }

        private static PlacementZone FindZone(IReadOnlyList<PlacementZone> zones, int zoneId)
        {
            if (zones == null) return null;
            for (int i = 0; i < zones.Count; i++)
                if (zones[i].ZoneId == zoneId) return zones[i];
            return zones.Count > 0 ? zones[0] : null;
        }

        private static Chromosome CloneChromosome(Chromosome src)
        {
            Chromosome c = new Chromosome
            {
                Fitness = src.Fitness,
                PlacedCount = src.PlacedCount
            };

            for (int i = 0; i < src.Genes.Count; i++)
                c.Genes.Add(CloneGene(src.Genes[i]));

            return c;
        }

        private static RackGene CloneGene(RackGene g)
        {
            return new RackGene
            {
                PositionX = g.PositionX,
                PositionZ = g.PositionZ,
                Rotation = g.Rotation,
                IsPlaced = g.IsPlaced,
                ZoneId = g.ZoneId,
                ModelIndex = g.ModelIndex,
            };
        }
    }
}