skaitiniai-metodai-labs/Lab2/main_3.py

from dataclasses import dataclass
from random import Random
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as patches

@dataclass
class Point:
    x: float
    y: float

    @staticmethod
    def rand(rand: Random, from_x: float, to_x: float, from_y: float, to_y: float):
        return Point(
            rand.uniform(from_x, to_x),
            rand.uniform(from_y, to_y)
        )

def gen_points(
        rand: Random,
        n: int,
        x_range = (-10, 10),
        y_range = (-10, 10)
    ):
    points = []
    while len(points) < n:
        point = Point.rand(rand, x_range[0], x_range[1], y_range[0], y_range[1])
        if point not in points:
            points.append(point)
    return points

def get_total_price(
        shops: list[Point],
        new_shops: list[Point],
        C,
        Cp
    ):
    total_price = 0
    for i, point in enumerate(new_shops):
        total_price += Cp(point.x, point.y)
        for other_point in shops:
            total_price += C(point.x, point.y, other_point.x, other_point.y)

        for j, other_point in enumerate(new_shops):
            if i == j: continue
            total_price += C(point.x, point.y, other_point.x, other_point.y)
    return total_price

def get_price_gradient(
        shops: list[Point],
        new_shops: list[Point],
        C,
        Cp,
        step = 0.001
    ):
    grad = []
    current_price = get_total_price(shops, new_shops, C, Cp)
    for i in range(len(new_shops)):
        new_shops[i].x += step
        new_price_x = get_total_price(shops, new_shops, C, Cp)
        new_shops[i].x -= step

        new_shops[i].y += step
        new_price_y = get_total_price(shops, new_shops, C, Cp)
        new_shops[i].y -= step

        grad.append(Point(
            new_price_x - current_price,
            new_price_y - current_price
        ))

    L = 0
    for grad_point in grad:
        L += grad_point.x**2 + grad_point.y**2
    L = L**0.5

    for grad_point in grad:
        grad_point.x /= L
        grad_point.y /= L

    return grad

def apply_gradient(points: list[Point], gradient: list[Point], step_size: float):
    for i, point in enumerate(points):
        point.x += step_size * gradient[i].x
        point.y += step_size * gradient[i].y

def gradient_descent(
        shops: list[Point],
        new_shops: list[Point],
        C,
        Cp,
        max_iterations = 100,
        step_size = 0.5,
        epsilon = 1e-6
    ):

    # iterations = []
    # price_over_iterations = []

    total_price = 1e10
    price_gradient = get_price_gradient(shops, new_shops, C, Cp)
    for iteration_idx in range(max_iterations):
        apply_gradient(new_shops, price_gradient, -step_size)

        new_total_price = get_total_price(shops, new_shops, C, Cp)
        # iterations.append(iteration_idx+1)
        # price_over_iterations.append(new_total_price)
        if abs(total_price - new_total_price) < epsilon:
            # plt.plot(iterations, price_over_iterations, linestyle='-', color='blue', label='Tikslo funkcija')
            # plt.legend()
            # plt.ylabel("Kaina")
            # plt.xlabel("Iteracija")

            # plt.show()
            # plt.waitforbuttonpress()
            return iteration_idx+1

        if total_price > new_total_price:
            total_price = new_total_price
        else:
            apply_gradient(new_shops, price_gradient, +step_size)
            price_gradient = get_price_gradient(shops, new_shops, C, Cp)
            step_size *= 0.9

    return -1

def main(
        N: list[Point],
        m: int,
        C,
        Cp,
        rand,
        max_iterations,
        step_size,
    ):
    shops = N
    new_shops = gen_points(rand, m)

    print("Starting price: ", get_total_price(shops, new_shops, C, Cp))

    iterations_used = gradient_descent(shops, new_shops, C, Cp, max_iterations, step_size)
    if iterations_used == -1:
        print("ERROR: Failed to reach minimum, not enough iterations")
        return

    print("Iterations: ", iterations_used)
    print("Minumum price: ", get_total_price(shops, new_shops, C, Cp))

    #plt.add_patch(patches.Rectangle((-10, -10), 20, 20, linestyle='--', facecolor='none', edgecolor='black'))
    plt.scatter(list(p.x for p in shops), list(p.y for p in shops), c="r", label="Esami")
    plt.scatter(list(p.x for p in new_shops), list(p.y for p in new_shops), c="b", label="Nauji")
    plt.legend()

    plt.xlabel("x")
    plt.ylabel("y")

    plt.show()

# Variantas: 10
rand = Random(3)
main(
    rand = rand,
    N = gen_points(rand, 20),
    m = 20,
    C = lambda x1, y1, x2, y2: np.exp(-0.3 * ((x1 - x2)**2 + (y1 - y2)**2)),
    Cp = lambda x1, y1: (x1**4 + y1**4)/1000 + (np.sin(x1) + np.cos(y1))/5 + 0.4,

    max_iterations = 1000,
    step_size=0.5
)