Untitled

 avatar
unknown
kotlin
a year ago
11 kB
5
Indexable
package com.example.projektmunka.routeOptimizer

import com.example.projektmunka.routeUtil.calculateRouteArea
import com.example.projektmunka.routeUtil.calculateRouteAscent
import com.example.projektmunka.routeUtil.calculateRouteLength
import com.example.projektmunka.routeUtil.countSelfIntersections
import com.example.projektmunka.data.Node
import com.example.projektmunka.data.Route
import org.jgrapht.Graph
import org.jgrapht.alg.shortestpath.DijkstraShortestPath
import org.jgrapht.graph.DefaultWeightedEdge
import java.util.Random
import kotlin.math.abs
import kotlin.math.min
import kotlin.math.pow

class CircularDifficultRouteOptimizer(
    private val graph: Graph<Node, DefaultWeightedEdge>,
    private val poiToClosestNonIsolatedNode: MutableMap<Node, Node>,
    private val keyPois: List<Node>,
    private val numKeyPois: Int,
    private val desiredRouteLength: Double,
    private val targetRouteAscent: Double,
    private val searchArea: Double,
    private val populationSize: Int,
    private val survivorRate: Int,
    private val maxGenerations: Int
) {

    private var population = mutableListOf<Route>()

    private fun initializePopulation(userLocation: Node) {
        population = generateInitialPopulation(keyPois, numKeyPois, populationSize, userLocation)
    }

    fun runGeneticAlgorithm(userLocation: Node): Route {

        initializePopulation(userLocation)

        val nChildren = (populationSize - survivorRate) / survivorRate

        repeat(maxGenerations) {
            val fitnessScores = population.map { route ->
                evaluateFitness(
                    userLocation,
                    route,
                    desiredRouteLength,
                    targetRouteAscent,
                    searchArea,
                    graph
                )
            }

            val selectedRoutes = selectNodes(population, fitnessScores, survivorRate).distinct()
            val newPopulation = mutableListOf<Route>()

            // Crossover: Create offspring routes by PMX crossover
            if (selectedRoutes.size >= 2) {
                val randomIndices = selectedRoutes.indices.shuffled().take(2)
                val parent1 = selectedRoutes[randomIndices[0]]
                val parent2 = selectedRoutes[randomIndices[1]]
                val cutPoints = Pair(1, 3)
                val offspring = PMXCrossover(parent1, parent2, cutPoints)

                val matchedPairs = mutableSetOf<Pair<Route, Route>>()

                for (parent in selectedRoutes) {
                    newPopulation.add(parent)
                    for (i in 0 until nChildren) {
                        var partner: Route

                        // Select random partner for crossover (ensuring they haven't been matched before)
                        do {
                            partner = selectedRoutes.random()
                        } while (partner == parent && selectedRoutes.size > 1)

                        // Add the current pair to the set of matched pairs
                        matchedPairs.add(Pair(parent, partner))

                        // Mutate offspring
                        val mutatedOffspring1 = exchangeMutation(offspring.first)
                        val mutatedOffspring2 = exchangeMutation(offspring.second)

                        // Randomly choose whether to add offspring1 or offspring2 to the new population
                        val addFirstOffSpring = (0..1).random()
                        if (addFirstOffSpring == 0) {
                            newPopulation.add(mutatedOffspring1)
                        } else {
                            newPopulation.add(mutatedOffspring2)
                        }
                    }
                }
            } else {
                for (parent in selectedRoutes) {
                    newPopulation.add(parent)

                    for (i in 0 until nChildren) {
                        newPopulation.add(exchangeMutation(parent))
                    }
                }
            }
            // Replace the old population with the new one
            population = newPopulation
        }


        val valtozoTesz = population.maxBy {
            evaluateFitness(
                userLocation,
                it,
                desiredRouteLength, // teszt
                targetRouteAscent,  // teszt nehézség, mennyire emelkedős az út
                searchArea,         // teszt
                graph
            )
        }!!

        // Calculate routh length
        val routeLength = calculateRouteLength(valtozoTesz) //teszt
        val maxWalkingTime = routeLength / 4
        println("GENERATED MaxwalkingTime: $maxWalkingTime")
        println("GENERATED Route Length: $routeLength")
        val routeAscent = calculateRouteAscent(valtozoTesz) //teszt
        println("GENERATED Route Ascent: $routeAscent")
        // Calculate the area of the polygon outlined by the route
        val searchArea = calculateRouteArea(valtozoTesz) //teszt
        println("GENERATED Search Area: $searchArea")

        //3 függvény meghívása a változóteszt-re és kiíratni


        return population.maxBy {
            evaluateFitness(
                userLocation,
                it,
                desiredRouteLength,
                targetRouteAscent,
                searchArea,
                graph
            )
        }!!
    }

    private fun generateInitialPopulation(
        keyPois: List<Node>,
        numKeyPois: Int,
        populationSize: Int,
        userLocation: Node
    ): MutableList<Route> {
        val initialPopulation = mutableListOf<Route>()
        val random = Random()

        repeat(populationSize) {
            val shuffledKeyPois = keyPois.shuffled(random)
            val route: MutableList<Node> =
                shuffledKeyPois.filter { it != userLocation }.take(numKeyPois).toMutableList()

            initialPopulation.add(Route(route))
        }
        return initialPopulation
    }

    private fun selectNodes(
        population: List<Route>,
        fitnessScore: List<Double>,
        survivorRate: Int
    ): List<Route> {

        val rankedNodes = population.zip(fitnessScore).sortedByDescending { it.second }
        return rankedNodes.take(survivorRate).map { it.first }
    }

    private fun evaluateFitness(
        userLocation: Node,
        route: Route,
        desiredRouteLength: Double,
        targetRouteAscent: Double,
        searchArea: Double,
        graph: Graph<Node, DefaultWeightedEdge>
    ): Double {
        val connectedRoute = connectPois(userLocation, route, graph)

        // Calculate total interestingness
        val beauty = route.path.sumOf { it.importance }

        // Calculate routh length
        val routeLength = calculateRouteLength(connectedRoute) //teszt

        // Calculate the number of self-intersections
        val selfIntersections = countSelfIntersections(connectedRoute.path)

        val routeAscent = calculateRouteAscent(connectedRoute) //teszt
        val ascentDelta = abs(routeAscent - targetRouteAscent)
        val ascentMultiplier = (1 - min(0.9, ascentDelta - routeAscent))

        // Calculate the area of the polygon outlined by the route
        val routeArea = calculateRouteArea(route) //teszt

        val areaMultiplier = routeArea / searchArea

        val distanceDelta = abs(routeLength - desiredRouteLength)
        val lengthMultiplier = (1 - min(0.9, distanceDelta - desiredRouteLength)).pow(2)

        val selfIntersectionMultiplier = 1.0 / (1 + selfIntersections)

        //return lengthMultiplier
        return beauty * lengthMultiplier * areaMultiplier * selfIntersectionMultiplier * ascentMultiplier
    }

    private fun PMXCrossover(
        parent1: Route,
        parent2: Route,
        cutPoints: Pair<Int, Int>
    ): Pair<Route, Route> {
        val size = parent1.path.size
        val offspring1 = MutableList<Node?>(size) { null }
        val offspring2 = MutableList<Node?>(size) { null }

        val (startIdx, endIdx) = cutPoints

        // Copy the segment between startIdx and endIdx from parent1 to offspring1 and from parent2 to offspring2
        for (i in startIdx..endIdx) {
            offspring1[i] = parent2.path[i]
            offspring2[i] = parent1.path[i]
        }

        for (i in 0 until size) {
            if (i < startIdx || i > endIdx) {
                var value1 = parent1.path[i]
                var value2 = parent2.path[i]

                while (offspring1.contains(value1)) {
                    val index = parent2.path.indexOf(value1)
                    value1 = parent1.path[index]
                }

                while (offspring2.contains(value2)) {
                    val index = parent1.path.indexOf(value2)
                    value2 = parent2.path[index]
                }

                // After the while loop, make sure value1 is not already in offspring1
                if (!offspring1.contains(value1)) {
                    offspring1[i] = value1
                }

                if (!offspring2.contains(value2)) {
                    offspring2[i] = value2
                }
            }
        }
        return Pair(
            Route(offspring1.toList() as MutableList<Node>),
            Route(offspring2.toList() as MutableList<Node>)
        )
    }

    private fun exchangeMutation(route: Route): Route {
        val random = Random()

        // Randomly select two distinct indices in the route
        var index1 = random.nextInt(route.path.size)
        var index2: Int

        do {
            index2 = random.nextInt(route.path.size)
        } while (index2 == index1)

        // Perform the exchange mutatuon by swapping the nodes at index1 and index2
        val mutatedRoute = route.path.toMutableList()
        val temp = mutatedRoute[index1]
        mutatedRoute[index1] = mutatedRoute[index2]
        mutatedRoute[index2] = temp

        return Route(mutatedRoute)
    }

    fun connectPois(
        userLocation: Node,
        pois: Route,
        graph: Graph<Node, DefaultWeightedEdge>
    ): Route {
        val dijkstra = DijkstraShortestPath(graph)
        val connectedRoute = Route(mutableListOf())

        connectedRoute.path.addAll(
            dijkstra.getPath(
                userLocation,
                poiToClosestNonIsolatedNode[pois.path.first()]
            ).vertexList
        )
        for (i in 0..pois.path.size - 2) {
            val current = pois.path[i]
            val next = pois.path[i + 1]

            val currentNonIsolated = poiToClosestNonIsolatedNode[current]
            val nextNonIsolated = poiToClosestNonIsolatedNode[next]

            connectedRoute.path.addAll(
                dijkstra.getPath(
                    currentNonIsolated,
                    nextNonIsolated
                ).vertexList
            )
        }
        connectedRoute.path.addAll(
            dijkstra.getPath(
                poiToClosestNonIsolatedNode[pois.path.last()],
                userLocation
            ).vertexList
        )

        return connectedRoute
    }
}
Editor is loading...
Leave a Comment