A Genetic Algorithm-based Beamforming Approach

在兹介紹一下所謂Beamforming(波束成型的天線陳列) 的架構,

自LTE通訊啓,基地台為了提供更佳的服務,故使用天線陣列來極化電磁波以利QoS的提升, 在5G的技術中, 幾乎其天缐唯一選項就是波束成型 (beamforming),  波束成型(Beamforming)技術可以大略的分成兩種:

第一種: 藉由量測到的通道係數, 設計傳送參數 (precoder), 最佳化通道

第二種: 透過多天線的相位偏移 (phase shifter), 決定電波傳遞強度模

本章節以Phase shifter 為其架構, 假設以1x9“矩陣”是線性代數來描述波束成型的天線陳列、

本文利用基因工程(Genetic Algorithm-based_來找出每一個Cell 的Weight以利其快速其值。

Source code with Python:

# -*- coding: utf-8 -*-

import numpy as np
import ga
import matplotlib.pyplot as plt
"""
The y=target is to maximize this equation ASAP:
    y = w1x1+w2x2+w3x3+w4x4+w5x5+6wx6+7Wx7+8Wx7+9Wx9
    where (x1,x2,x3,x4,x5,x6,x7,x8,x9)=(4,-2,3.5,5,-11,-4.7,5.0,2.1,3.1)
    What are the best values for the 9 weights w1 to w9?
    We are going to use the genetic algorithm for the best possible values after a number of generations.
"""

# Inputs of the equation.
equation_inputs = [4,-2,3.5,5,-11,-4.7,5.0,2.1,3.1]

# Number of the weights we are looking to optimize.
num_weights = len(equation_inputs)

"""
Genetic algorithm parameters:
    Mating pool size
    Population size
"""
sol_per_pop = 8
num_parents_mating = 4

# Defining the population size.
pop_size = (sol_per_pop,num_weights) # The population will have sol_per_pop chromosome where each chromosome has num_weights genes.
#Creating the initial population.
new_population = np.random.uniform(low=-4.0, high=4.0, size=pop_size)
print("new_population")
print(new_population)

"""
new_population[0,:]=[[ 2.58108145  2.42053643 -3.24720098  0.73414778  2.95861561 -3.95613747
   2.34638506 -1.96226993 -2.4267999 ]
new_population[1,:]= [ 0.50988501  3.66384758 -0.35728906 -3.36106177  0.60748192  0.34572714
   0.63256316  3.59916985  0.5291632 ]
new_population[2,:]= [-3.99726266 -1.05382206 -0.72618039 -0.69354415  3.6819675   1.42235044
   3.21944868  0.56545786 -2.53333267]
new_population[3,:]= [-2.01602033  3.21295543  0.1898793  -2.6094637   1.9595066  -2.04175245
  -0.63172776 -1.84656932 -3.39214779]
new_population[4,:]= [-1.65667992 -3.61456147 -2.08880869  0.51076383  0.06322565 -0.43551276
  -3.4748497  -2.61883376  2.93387284]
new_population[5,:]= [ 3.06194594 -1.81691236 -3.5244207   3.7688676  -0.78804301  1.7642483
  -1.63477098  2.0739781  -3.88904675]
new_population[6,:]= [-0.7733979  -0.59532673  0.22656214 -1.53837445 -1.72333473 -1.32000815
   1.8188883  -0.8669669  -1.29803437]
new_population[7,:]= [-3.52687898 -3.91602606  2.07969841 -2.29166193  0.58104485  0.79150089
  -3.13136887 -0.04240155  2.80654781]]
"""

best_outputs = []
num_generations = 10
for generation in range(num_generations):
    print("Generation : ", generation)
    # Measuring the fitness of each chromosome in the population.
    fitness = ga.cal_pop_fitness(equation_inputs, new_population)
    print("Fitness")
    print(fitness)

    best_outputs.append(np.max(numpy.sum(new_population*equation_inputs, axis=1)))
    # The best result in the current iteration.
    print("Best result : ", np.max(np.sum(new_population*equation_inputs, axis=1)))
    
    # Selecting the best parents in the population for mating.
    parents = ga.select_mating_pool(new_population, fitness, 
                                      num_parents_mating)
    print("Parents")
    print(parents)

    # Generating next generation using crossover.
    offspring_crossover = ga.crossover(parents,
                                       offspring_size=(pop_size[0]-parents.shape[0], num_weights))
    print("Crossover")
    print(offspring_crossover)

    # Adding some variations to the offspring using mutation.
    offspring_mutation = ga.mutation(offspring_crossover, num_mutations=2)
    print("Mutation")
    print(offspring_mutation)

    # Creating the new population based on the parents and offspring.
    new_population[0:parents.shape[0], :] = parents
    new_population[parents.shape[0]:, :] = offspring_mutation
    
# Getting the best solution after iterating finishing all generations.
#At first, the fitness is calculated for each solution in the final generation.
fitness = ga.cal_pop_fitness(equation_inputs, new_population)
# Then return the index of that solution corresponding to the best fitness.
best_match_idx = np.where(fitness == np.max(fitness))

print("Best solution : ", new_population[best_match_idx, :])
print("Best solution fitness : ", fitness[best_match_idx])



plt.plot(best_outputs)
plt.xlabel("Iteration")
plt.ylabel("Fitness")

plt.show()

                                     

Route Planning  With  Genetic Algorithm

Since we are given each location’s coordinates, let’s calculate the Manhattan distances between each pair of points and count the longitude and latitude differences to get a sense of direction . We can clean up timestamps a little and keep the original features which might look useless to us at first glance.

Locs : Traveler to go cities  list (note that locs is a list containing Location objects)
Level: number of evolution
Population : refers to a group consisting of several different paths
Variant  :  it is as the degree of variation between parents and children
Mutate_percent: refers to  percentage of a path is  mutated

Elite_save_percent : The shortest  path is regarded as the elite path (0.1 = 10% here)

At first, to define the  location:

 locations = []
    #longitude and latitude
    xs = [8, 50, 18, 35, 90, 40, 84, 74, 34, 40, 60, 74]
    ys = [3, 62, 0, 25, 89, 71, 7, 29, 45, 65, 69, 47]
    cities = ['Z', 'P', 'A', 'K', 'O', 'Y', 'N', 'X', 'G', 'Q', 'S', 'J']
    for x, y, name in zip(xs, ys, cities):
          locations.append(Location(name, x, y))

    my_locs=  locations

 Source code  with Python as below: 


import random as rd
import copy
from matplotlib import pyplot as plt

    
    

class Location:
    
    def __init__(self, name, x, y):
        self.name = name
        self.loc = (x, y)

    def distance_between(self, location2):
        assert isinstance(location2, Location)
        return ((self.loc[0] - location2.loc[0]) ** 2 + (self.loc[1] -                                      location2.loc[1]) ** 2) ** (1 / 2)
         
        
class Route:
    
    def __init__(self, path):
        # path is a list of Location obj
        self.path = path
        self.length = self._set_length()

    def _set_length(self):
        total_length = 0
        path_copy = self.path[:]
        from_here = path_copy.pop(0)
        init_node = copy.deepcopy(from_here)
        while path_copy:
            to_there = path_copy.pop(0)
            total_length += to_there.distance_between(from_here)
            from_here = copy.deepcopy(to_there)
        total_length += from_here.distance_between(init_node)
        return total_length
        
class GeneticAlgo:
    
    def __init__(self, locs, level=10, populations=100, variant=3, mutate_percent=0.01, elite_save_percent=0.1):
        self.locs = locs
        self.level = level
        self.variant = variant
        self.populations = populations
        self.mutates = int(populations * mutate_percent)
        self.elite = int(populations * elite_save_percent)
        
    def _find_path(self):
        # locs is a list containing all the Location obj
        locs_copy = self.locs[:]
        path = []
        while locs_copy:
            to_there =                                                                locs_copy.pop(locs_copy.index(rd.choice(locs_copy)))
            path.append(to_there)
        return path

    def _init_routes(self):
        routes = []
        for _ in range(self.populations):
            path = self._find_path()
            routes.append(Route(path))
        return routes
        
    def _get_next_route(self, routes):
        routes.sort(key=lambda x: x.length, reverse=False)
        elites = routes[:self.elite][:]
        crossovers = self._crossover(elites)
        return crossovers[:] + elites

    def _crossover(self, elites):
        # Route is a class type
        normal_breeds = []
        mutate_ones = []
        for _ in range(self.populations - self.mutates):
            father, mother = rd.sample(elites[:4], k=2)
            index_start = rd.randrange(0, len(father.path) - self.variant - 1)
            # list of Location obj
            father_gene = father.path[index_start: index_start + self.variant]
            father_gene_names = [loc.name for loc in father_gene]
            mother_gene = [gene for gene in mother.path if gene.name not in father_gene_names]
            mother_gene_cut = rd.randrange(1, len(mother_gene))
            # create new route path
            next_route_path = mother_gene[:mother_gene_cut] + father_gene + mother_gene[mother_gene_cut:]
            next_route = Route(next_route_path)
            # add Route obj to normal_breeds
            normal_breeds.append(next_route)

            # for mutate purpose
            copy_father = copy.deepcopy(father)
            idx = range(len(copy_father.path))
           # gene1, gene2 = rd.shuffle(idx)
            gene1, gene2 = rd.sample(idx, 2)
            copy_father.path[gene1], copy_father.path[gene2] = copy_father.path[gene2], copy_father.path[gene1]
            mutate_ones.append(copy_father)
        mutate_breeds = rd.sample(mutate_ones, k=self.mutates)
        return normal_breeds + mutate_breeds  
           
    def evolution(self):
        routes = self._init_routes()
        for _ in range(self.level):
            routes = self._get_next_route(routes)
        routes.sort(key=lambda x: x.length)
        return routes[0].path, routes[0].length
    
    
  
     
if __name__ == '__main__':
    # obj = GeneticAlgo()
    
    locations = []
    xs = [8, 50, 18, 35, 90, 40, 84, 74, 34, 40, 60, 74]
    ys = [3, 62, 0, 25, 89, 71, 7, 29, 45, 65, 69, 47]
    cities = ['Z', 'P', 'A', 'K', 'O', 'Y', 'N', 'X', 'G', 'Q', 'S', 'J']
    for x, y, name in zip(xs, ys, cities):
          locations.append(Location(name, x, y))
    my_locs=  locations
       

    my_algo =  GeneticAlgo(my_locs, level=40, populations=150,                variant=2, mutate_percent=0.02, elite_save_percent=0.15)

    variant=2, mutate_percent=0.02, elite_save_percent=0.15)

    best_route, best_route_length = my_algo.evolution()

    best_route.append(best_route[0])

    print([loc.name for loc in best_route], best_route_length)

    print([(loc.loc[0], loc.loc[1]) for loc in best_route],                                                                             best_route_length)   

    fig, ax = plt.subplots()

    ax.plot([loc.loc[0] for loc in best_route], [loc.loc[1] for loc in                               best_route], 'red', linestyle='-', marker='')

    ax.scatter(xs, ys)

    for i, txt in enumerate(cities):

        ax.annotate(txt, (xs[i], ys[i]))

    plt.show()