Zero order methods

Zero order methods

  1. Implement Rastrigin function f: \mathbb{R}^d \to \mathbb{R} for d = 10. link

    f(\mathbf{x})=10 d+\sum_{i=1}^{d}\left[x_{i}^{2}-10 \cos \left(2 \pi x_{i}\right)\right]

    • Consider global optimization from here.
    • Plot 4 graphs for different d from {10, 100, 1000, 10000}. On each graph you are to plot f from N_{fev} for 5 methods: basinhopping, brute, differential_evolution, shgo, dual_annealing from scipy, where N_{fev} - the number of function evaluations. This information is usually available from specific_optimizer.nfev. If you will need bounds for the optimizer, use x_i \in [-5, 5].
    • Note, that it is crucial to fix seed and to use the same starting point for fair comparison.
  2. Machine learning models often have hyperparameters. To choose optimal one between them one can use GridSearch or RandomSearch. But these algorithms computationally uneffective and don’t use any sort of information about type of optimized function. To overcome this problem one can use bayesian optimization. Using this method we optimize our model by sequentially chosing points based on prior information about function.


    In this task you will use optuna package for hyperparameter optimization RandomForestClassifier. Your task is to find best Random Forest model varying at least 3 hyperparameters on iris dataset. Examples can be find here or here

    !pip install optuna
    import sklearn.datasets
    import sklearn.ensemble
    import sklearn.model_selection
    import sklearn.svm
    import optuna
    iris = sklearn.datasets.load_iris()
    x, y =,
  3. Try to perform hyperparameter optimization in context of any metric for imbalanced classification problem with optuna and keras. Open In Colab{: .btn }

  4. Let’s arrange the base stations of the wireless network optimally! Suppose you have N_{obj} = 10 clusters of 10 subscribers each. Let us use a genetic algorithm to gradually search for the optimal number and location of base stations in order to minimize the cost of arranging such stations.

    Below is one possible implementation of the genetic algorithm.


    This is a list of arrays of size [N_stations x 2]. Each individual in this case is a set of station coordinates on the plane. Generation of a random


    Defined by the function mutation(). A mutation_rate part is selected from all individuals and a random Gaussian noise is added to the mutation_rate part of its stations. An individual with a random number of stations with random coordinates is then added to the population.


    Defined by children_creation() and breed(). Two sets of stations are matched with a third station, from which the even stations of one parent and the odd stations of the other are taken.

    Estimation of the value of an individual

    Defined by evaluate_generation(). The total cost corresponding to a particular individual is made up of the cost of building base stations (each cost station_cost) minus the profit from each client. The profit from each client is inversely proportional to the distance to “his” base station. Each customer joins only one (closest) base station using find_nearest_station(). In addition, the profit from each subscriber is inversely proportional to the number of subscribers at a given base station (each station has the number of subscribers stations_load connected to it). Note also that, starting from a certain proximity to the subscriber to the base station, the client’s profit ceases to grow (in our algorithm, it is the same in the radius of 0.1 from the base station, then linearly decreases).

    Your task is to come up with any modifications to the proposed procedures within the genetic algorithm so that the final quality of the algorithm is better. Suggest, describe, and test ideas for improving the algorithm.

    %matplotlib notebook
    import numpy as np
    from scipy.spatial.distance import cdist
    from random import shuffle, sample
    from copy import deepcopy
    import random
    from plotly.subplots import make_subplots
    import plotly.graph_objects as go
    from IPython.display import clear_output
    import matplotlib.pyplot as plt
    def generate_problem(N_obj, N_abon_per_cluster):
        abonents = np.zeros((N_obj*N_abon_per_cluster,2))
        for i_obj in range(N_obj):
            center = np.random.random(2)
            cov    = np.random.random((2,2))*0.1
            cov    = cov @ cov.T
            xs, ys = np.random.multivariate_normal(center, cov, N_abon_per_cluster).T
            abonents[i_obj*N_abon_per_cluster:(i_obj+1)*N_abon_per_cluster, 0] = xs
            abonents[i_obj*N_abon_per_cluster:(i_obj+1)*N_abon_per_cluster, 1] = ys
        return abonents
    def plot_problem(abonents):
        plt.plot(abonents[:,0], abonents[:,1], 'go')
        plt.title('The village')
    #     plt.savefig('bs_problem.svg')
    def random_solution(abonents, N_solutions = 100):
        x_min, x_max = abonents[:,0].min(), abonents[:,0].max()
        y_min, y_max = abonents[:,1].min(), abonents[:,1].max()
        population = []
        for i_sol in range(N_solutions):
            N_stations = int(np.random.random(1)[0]*10)+1
            stations = np.zeros((N_stations,2))
            stations[:,0], stations[:,1] = np.random.random(N_stations)*(x_max - x_min), np.random.random(N_stations)*(y_max - y_min)
        return population
    def find_nearest_station(dist_matrix):
        return np.argmin(dist_matrix, axis=1)
    def pairwise_distance(abonents, stations):
        return cdist(abonents, stations)
    def evaluate_generation(abonents, population, station_cost = 1, abonent_profit_base = 1):  
        costs = []
        for creature in population:
            N_stations, N_users = len(creature), len(abonents)
            total_cost          = N_stations*station_cost
            dist_matrix         = pairwise_distance(abonents, creature)
            stations_assignment = find_nearest_station(dist_matrix)
            stations_load       = np.ones(N_stations)
            stations_load       = np.array([1/(sum(stations_assignment == i_st)+1) for i_st, st in enumerate(stations_load)])
            for i_ab, abonent in enumerate(abonents):
                dist_to_base = dist_matrix[i_ab, stations_assignment[i_ab]]
                total_cost  -= stations_load[stations_assignment[i_ab]]*abonent_profit_base/(max(0.1, dist_to_base))
        return np.array(costs)
    def mutation(population, mutation_rate = 0.3):
        N_creatures = len(population)
        x_min, x_max = -1, 1
        y_min, y_max = -1, 1
        mutated_creatures = sample(range(N_creatures), int(mutation_rate*N_creatures))
        for i_mut in mutated_creatures:
            N_stations = len(population[i_mut])
            mutated_stations = sample(range(N_stations), int(mutation_rate*N_stations))
            for i_st_mut in mutated_stations:
                population[i_mut][i_st_mut] += np.random.normal(0, 0.01, 2)
        N_new_stations = max(1, int(random.random()*mutation_rate*N_creatures))
        for i in range(N_new_stations):
            new_stations = np.zeros((N_new_stations,2))
            new_stations[:,0], new_stations[:,1] = np.random.random(N_new_stations)*(x_max - x_min), np.random.random(N_new_stations)*(y_max - y_min)
        return population
    def children_creation(parent1, parent2):
        # whoisbatya
        batya = random.random() > 0.5
        if batya:
            child = np.concatenate((parent1[::2], parent2[1::2]))
            child = np.concatenate((parent1[1::2], parent2[::2]))
        return np.array(child)
    def breed(population):
        new_population = deepcopy(population)
        N_creatures = len(population)
        for i in range(N_creatures//2):
            children = children_creation(population[i], population[i+1])
        return new_population
    def selection(abonents, population, offsprings = 10):
        scores = evaluate_generation(abonents, population)
        best = np.array(scores).argsort()[:offsprings].tolist()
        return [population[i_b] for i_b in best], population[best[0]] 
    def let_eat_bee(N_creatures, N_generations, N_obj = 10, N_abon_per_cluster = 10):
        abonents = generate_problem(N_obj, N_abon_per_cluster)
        costs_evolution = np.zeros((N_generations, N_creatures))
        population = random_solution(abonents, N_creatures)
        best_creatures = []
        for generation in range(N_generations):
            population                = mutation(population)
            population                = breed(population)
            population, best_creature = selection(abonents, population, N_creatures)
            costs_evolution[generation, :] = evaluate_generation(abonents, population)
            # Plotting
            x_min, x_max = 0, 1
            y_min, y_max = 0,1
            cost_min  = [np.min(costs_evolution[i])  for i in range(generation)]
            cost_max  = [np.max(costs_evolution[i])  for i in range(generation)]
            cost_mean = [np.mean(costs_evolution[i]) for i in range(generation)]
            fig = make_subplots(rows=1, cols=2, subplot_titles=("Topology of the best solution", "Cost function"))
            fig.update_xaxes(title_text="x", range = [x_min,x_max],  row=1, col=1)
            fig.update_yaxes(title_text="y", range = [y_min,y_max], row=1, col=1)
            fig.update_yaxes(title_text="Total cost", row=1, col=2)
            fig.update_xaxes(title_text="Generation", row=1, col=2)
                go.Scatter(x=abonents[:, 0], y=abonents[:, 1], mode='markers', name='abonents',  marker=dict(size=5)),
                row=1, col=1
                go.Scatter(x=best_creatures[generation][:, 0], y=best_creatures[generation][:, 1], mode='markers', name='stations', marker=dict(size=15)),
                row=1, col=1
                go.Scatter(x = list(range(generation)), y = cost_min, name='best'),
                row=1, col=2
                go.Scatter(x = list(range(generation)), y = cost_max, name='worst'),
                row=1, col=2
                go.Scatter(x = list(range(generation)), y = cost_mean, name='mean'),
                row=1, col=2
        return costs_evolution, abonents, best_creatures
    costs_evolution, abonents, best_creatures = let_eat_bee(200, 200)