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()                    

                     退休生活如何規劃財務

              按滙豐集團曾經公布一份「未來的退休生活」調查結果，它們在16個國家調查超過1萬8000名受訪者。調查發現：全球超過31%已退休人士表示，他們很後悔沒有提早為退休做準備。而台灣已退休人士，後悔沒有提早為退休做準備的比率高達51%，排名全球第一。

人生短短歳月，從娃兒啟程至人生終點短則數十年，長則百年。如何安排有尊嚴的退休生活應是一門課程。

圖1: 退休族的迷失(取自https://money.udn.com/money/story/12040/4443550#prettyPhoto)

在此就筆者的經驗分享給即將準備退休的參考。综觀各式理財工具， 股市，基金及房價等歷年波動曲線圖，

臺灣因淺碟經濟，靠外銷謀生故股海中，隨著消息面坑殺散戶時有所聞，且內線交易一直是臺灣股市處於大戶及公司派的暗器，在消息不透明及經營者惡意欺騙。甚小有散戶獲利。故股海如死海般只會讓散戶鎩羽而歸！

如下圖股市因外在的變動，台股近30年加權指數變化比房市變動劇烈。在準備退休的人士除非看清股市波動，一般建議你買的是定存股 ，即股價變動小且每年有比定存高的股利收入。

圖2: 台股 30年 (取自CMoney 月刋)

反觀台灣房市波動較少，房市30年來除了SARS 期間有修正之外其指數尚维持正成長。在房市要獲利需

要一些基本功，首重地區，交通便捷及生活機能。可在蛋黃區中物色相對便宜的屋件。房子外觀及屋齡非重點，重點是入手的價格需低於

周邊物件就有獲利空間。也許用於自住或出租因其控制權100%由自己調控。故我個人大部份資產放置於房市，透過出租來維持財務自由度。

圖3: 台灣房價指數 (取自https://group.dailyview.tw/article/detail/833)

                                 

Convert binary to decimal  with Python 

Well! how to convert binary to decimal

For binary number with n digits:

dn-1 ... d3 d2 d1 d0

The decimal number is equal to the sum of binary digits (dn) times their power of 2 (2n):

decimal = d0×20 + d1×21 + d2×22 + ...

There list the sample code of python 

def binaryToDecimal(binary): 

   i = 0

   dec=0

   length=len(binary)

   #print("length")

   #print(length)

   while i< length: 

       if binary[i]=='1':

         dec=dec+2**(length-i)

         #print("dec")

         #print(dec)

       else:

         dec=dec

        # dec = binary % 10

       # decimal = decimal + dec * pow(2, i) 

       # binary = binary//10

       i += 1

   

   return dec    

input binary code :['0', '1', '0', '0', '1', '1', '1', '1', '0', '1', '0', '0', '0', '1', '1', '1', '1', '1', '1', '0', '1', '1', '1', '0', '1', '1', '1', '0', '1', '0', '1', '1']

output decimal code:  1,330,114,283‬

                                                           

                                

   基因演算法(Genetic Algorithms)

         基因演算法，其哲學理論就是達爾文那套優勝劣汰適者生存的進化理論的思想。一個種群，通過長時間的繁衍，種群的基因會向著更適應環境的趨勢進化，適應性強的個體基因被保留，後代越來越多，適應能力低個體的基因被淘汰，後代越來越少。經過幾代的繁衍進化，留下來的少數個體，就是相對能力最強的個體了。

        目前用數學來導出進化模式,用亂數先産生一组亞當與夏娃初始基因排序值,再利用優生理論選出最優基, 本文選擇方法是用機率分佈的所謂輪盤法（Roulette Wheel Selection）來選擇。後續善用自然生態演變的兩種模式 ,突變及交配産出最優的基因?原則上引用多組基因透過亂數來仿真突變及交配産出最優的基因? 但在虚擬環境中畢竟少了真實環境的因子，也造成基因演算法的區域性搜尋能力較差，導致單純的遺傳演算法比較費時，在進化後期搜尋效率較低。在實際應用中，遺傳演算法容易產生過早收斂的問題。

本文的函式如下:

流程圖如下:

Genetic Algorithms with python code 

import numpy as np

import math

import ga

import matplotlib.pyplot as plt

chromosome_length = 33

population_size = 500

best_outputs = []

num_generations = 20

best_score_progress = [] # Tracks progress

next_population=[]

reference = ga.create_reference_solution(chromosome_length)

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, testnew_population)

    fitness = ga.cal_pop_fitness(xnew_population,ynew_population)

    print("fitness")

    print(fitness)

    f_population=np.concatenate((v_population, fitness), axis=1)

    print("f_population")

    print(f_population)

    #best_outputs.append(numpy.max(numpy.sum(testnew_population*equation_inputs, axis=1)))

    best_outputs.append(np.max(fitness))

    # The best result in the current iteration.

    #print("Best result : ", numpy.max(numpy.sum(testnew_population*equation_inputs, axis=1)))

    print("Best result : ", np.max(fitness))

    # 

    # Selecting the best parents in the population for mating.

    total_fitness=np.sum(fitness)

    print("total_fitness")

    print(total_fitness)

    

    #to caculation orbaally of fitness

    prob_select=fitness/total_fitness

    print("prob_select")

    print(prob_select)

    

    prob_list=ga.get_probability_list(fitness)

    prob_list=np.array(prob_list)

    print("prob_list")

    print(prob_list)

    

    #print("relative_fitness")

    #print(ga.get_probability_list)

    

    parents=ga.roulette_wheel_pop(v_population,prob_list,10)

    parents=np.array(parents)

    print("Parents")

    print(parents)

    #parents = ga.select_mating_pool(v_population, fitness, num_parents_mating)

    # print("Parents")

    #print(parents)

    

    #parents=list[parents]

    parent1=ga.random_pop(parents,10)

    print("Parent1")

    print(parent1)

    parent1=np.array(parent1)

    #parent1=parent1[1][0]

    #print("Parent1")

    #print(parent1)

    

    parents = parents.view([('', parents.dtype)] * parents.shape[1])

    parent1 = parent1.view([('', parent1.dtype)] * parent1.shape[1])

    

    parent=np.setdiff1d(parents,parent1).view(parents.dtype).reshape(-1, parents.shape[1])

    print("Parent")

    print(parent)

    parent2=ga.random_pop(parent,10)

    print("Parent1")

    print(parent1)

    print("Parent2")

    print(parent2)

    parent1=np.array(parent1)

    parent2=np.array(parent2)

    # to binary code

    parent1_bin=ga.trans_binary(parent1)

    parent2_bin=ga.trans_binary(parent2)

    print("Parent1_bin")

    print(parent1_bin)

    print("Parent2_bin")

    print(parent2_bin)

    """

    child=(ga.breed_by_crossover(parent1_bin, parent2_bin))

    chide1=child[0]

    chide2=child[1]

    print("chide1")

    print(chide1)

    print("chide2")

    print(chide2)

    """

    new_population=[0]

    child_1, child_2 = ga.breed_by_crossover(parent1_bin, parent2_bin)

    #x1=' '.join(format(child_1, 'b') for x in bytearray(child_1))

    x1=child_1[0]

    x1=' '.join(format(x, 'b') for x in bytearray(x1))

    x3=child_1[1]

    x3=' '.join(format(x, 'b') for x in bytearray(x3))

    

    x2=child_2[0]

    x2=' '.join(format(x, 'b') for x in bytearray(x2))

    x4=child_2[1]

    x4=' '.join(format(x, 'b') for x in bytearray(x4))

    

    #for i in xrange(k):

    #    print(x1[i])

    child_1=ga.rebinary(x1,x3)

    #child_1.append(ga.rebinary(x3))

    child_2=ga.rebinary(x2,x4)

    #child_2.append(ga.rebinary(x4))

     

    

    #xx1=np.array(xx1)

    #xx3=np.array(xx3)

    #child_1=np.array(child_1)

    #child_2=np.array(child_2)

    print("child_1")

    print(child_1)                                                                   

    print("child_2")

    print(child_2)

    #child_1=np.concatenate(xx1,xx3)

    #child_1 = child_1.view([('', child_1.dtype)] * child_1.shape[1])

    #child_2 = child_2.view([('', child_2.dtype)] * child_2.shape[1])

    #print("child_1")

    #                                                                                                  print(child_1)

    chile_1,chile_2 = ga.breed_by_mutation(child_1,child_2)

    new_population=child_1

    new_population.append(child_2)

    print("new_population")

    print(new_population)

    # Replace the old population with the new one

    New_x1= ga.binaryToDecimal(child_1[:17])

    New_x2= ga.binaryToDecimal(child_1[18:])

    New_y1= ga.binaryToDecimal(child_2[:17])

    New_y2= ga.binaryToDecimal(child_2[18:])

    #New_x1= int(child_1[:18])

    #New_x2= int(child_1[18:])

    #New_y1= int(child_2[:18])

    #New_y2= int(child_2[18:])

    print("New+x1")

    print(New_x1)  

    print("New+x2")

    print(New_x2)  

    print("New_y1")

    print(New_y1) 

    print("New_y2")

    print(New_y2)                                                      

    child_x1=-3.0+New_x1*(12.1-(-3.0))/(2**17)-1

    child_x2=4.1+New_x2*(5.8-4.1)/(2**15)-1

    child_y1=-3.0+New_y1*(12.1-(-3.0))/(2**17)-1

    child_y2=4.1+New_y2*(5.8-4.1)/(2**15)-1

    print("child_x1")

    print(child_x1)  

    print("child_x2")

    print(child_x2)  

    print("child_y1")

    print(child_y1)  

    print("child_y2")

    print(child_y2)  

    child=np.random.ranf(size=(2,2))

   

    child[0,0]=child_x1

    child[0,1]=child_x2

    child[1,0]=child_y1

    child[1,1]=child_y2

       

    print("child")

    print(child)  

   # print("child_2")

   # print(child_2)  

    print("parent")

    print(parent1[0,0])

    parentn=np.random.ranf(size=(2,2))

    x=parent1[0,0]

    parentn[0,0]=x[0]

    parentn[0,1]=x[1]

    x=parent2[0,0]

    parentn[1,0]=x[0]

    parentn[1,1]=x[1]

    

   # parents.append(parent2)

    print("parent")

    print(parentn)

     

   

    new_population=np.array(new_population)

    #next_poulation=ga.randomly_mutate_population(new_population,0.1)

    #print("Next_population")

    #print(next_population)

      

    #new_population[parents.shape[0]:, :] = offspring_mutation

    # Creating the new population based on the parents and offspring.

    print("old_poulation")

    print(v_population)

    random_point = int(np.random.uniform(1, 7, 1))

    v_population[random_point,0] = parentn[0,0]

    v_population[random_point,1] = parentn[0,1]

    v_population[random_point+1,0] = parentn[1,0]

    v_population[random_point+1,1] = parentn[1,1]

    v_population[random_point+2,0] = child[0,0]

    v_population[random_point+2,1] = child[0,1]

    v_population[random_point+3,0] = child[1,0]

    v_population[random_point+3,1] = child[1,1]

    print("new_poulation")

    print(v_population)

   # v_population[parents.shape[0]:, :] = child

    #xnew_population=np.hsplit(v_population, 2, axis=0)

    #ynew_population=np.hsplit(v_population, 2, axis=1)

    num_repat=10

    for i in np.arange(num_repat): 

        xnew_population[i]=v_population[i][0]

        ynew_population[i]=v_population[i][1]

      

# 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(xnew_population,ynew_population)

# Then return the index of that solution corresponding to the best fitness.

    best_match_idx = np.where(fitness == np.max(fitness))

    f_population=np.concatenate((v_population, fitness), axis=1)

    best_score=fitness[best_match_idx]

    print("1st generation f_population")

    print(f_population)

    print("Best solution : ", v_population[best_match_idx, :])

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

    best_score_progress.append(best_score)

plt.plot(best_score_progress)

plt.xlabel('Generation')

plt.ylabel('Best score (% target)')

plt.show()