DiscreteHillClimbing

การปีนเขาที่ไม่ต่อเนื่อง

แพ็คเกจนี้ (จาก DPEA) ให้การดำเนินการของอัลกอริทึมการปีนเขาสำหรับงานที่ไม่ต่อเนื่อง

 pip install DiscreteHillClimbing

• การปีนเขาที่ไม่ต่อเนื่อง
  • เกี่ยวกับ
  • ทำไมต้องปีนเขา?
  • Pseudocode
  • กระบวนการทำงาน
  • พารามิเตอร์
  • ตัวอย่าง
    • จำนวนการค้นหาแบบสุ่มของตัวเอง
    • ขั้นตอนโลภที่แตกต่างกัน

เกี่ยวกับ

การปีนเขาฮิลล์ ( ประสานงานการประสานงาน ) เป็นอัลกอริทึมที่ง่ายที่สุดสำหรับงานที่ไม่ต่อเนื่องมาก (หนึ่งที่ง่ายกว่านั้นได้รับการสุ่มดีที่สุดเท่านั้น) ในงานที่ไม่ต่อเนื่องแต่ละตัวทำนายสามารถมีค่าของมันจากชุด จำกัด ดังนั้นเราสามารถตรวจสอบค่าทั้งหมดของตัวทำนาย (ตัวแปร) หรือบางส่วนที่ไม่สุ่มเล็ก ๆ ของมันและทำการปรับให้เหมาะสมโดยตัวทำนายหนึ่งตัว หลังจากนั้นเราสามารถปรับให้เหมาะสมโดยตัวทำนายอื่นและอื่น ๆ นอกจากนี้เราสามารถลองหาวิธีแก้ปัญหาที่ดีกว่าโดยใช้ 1, 2, 3, ... ทำนายและเลือกการกำหนดค่าที่ดีที่สุดเท่านั้น

มีหลายวิธีในการตระหนักถึง การปีนเขาบนเนินเขา ดังนั้นฉันจึงพยายามใช้งานที่เรียบง่ายและเป็นสากล แน่นอนว่ามันจะเป็นการดีกว่าที่จะสร้างการใช้งาน (เร็วขึ้น) ของคุณขึ้นอยู่กับงานเฉพาะของ UR แต่แพ็คเกจนี้เป็นตัวเลือกที่ยืดหยุ่นที่ดีสำหรับการเริ่มต้น

ทำไมต้องปีนเขา?

การปีนเขาฮิลล์เป็นพื้นฐานที่สมบูรณ์แบบเมื่อคุณเริ่มหาทางออก มันช่วยได้จริงๆและมันจะทำให้คุณได้ผลลัพธ์ที่ดีมากโดยใช้การประเมินฟังก์ชั่นเพียง 50-200

Pseudocode

ดูแนวคิดหลักของการใช้งานของฉันใน pseudocode นี้:

 best solution < - start_solution
best value < - func ( start_solution )

while functions evaluates_count < max_function_evals :
    predictors < - get greedy_step random predictors ( variables )
    for each predictor from predictors :
        choose random_counts_by_predictors values from available values of this predictor
        for each chosen value :
            replace predictor value with chosen
            evaluate function
        remember best result as result of this predictor
    select best predictor with its best configuration
    replace values in solution
    it is new best solution 

กระบวนการทำงาน

โหลดแพ็คเกจ :

 import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descent

กำหนดฟังก์ชั่นที่ดีที่สุด :

 def func ( array : np . ndarray ) -> float :
    return ( np . sum ( array ) + np . sum ( array ** 2 )) / ( 1 + array [ 0 ] * array [ 1 ])

กำหนดชุดที่มีอยู่สำหรับแต่ละตัวทำนาย :

 available_predictors_values = [
    np . array ([ 10 , 20 , 35 , 50 ]),
    np . array ([ - 5 , 3 , - 43 , 0 , 80 ]),
    np . arange ( 40 , 500 ),
    np . linspace ( 1 , 100 , num = 70 ),
    np . array ([ 65 , 32 , 112 ]),
    np . array ([ 1 , 2 , 3 , 0 , 9 , 8 ]),
    np . array ([ 1 , 11 , 111 , 123 , 43 ]),
    np . array ([ 8 , 9 , 0 , 5 , 4 , 3 ]),
    np . array ([ - 1000 , - 500 , 500 , 1000 ])
]

สร้างวิธีแก้ปัญหา :

 solution , value = Hill_Climbing_descent ( function = func ,
    available_predictors_values = available_predictors_values ,
    random_counts_by_predictors = 4 ,
    greedy_step = 1 ,
    start_solution = None ,
    max_function_evals = 1000 ,
    maximize = False ,
    seed = 1 )

print ( solution )
print ( value )

# [  10.           -5.          493.           98.56521739  112.    9.          123.            9.         1000.        ]
# -26174.972801975237 

พารามิเตอร์

• function : func np.array-> float/int; ฟังก์ชั่นที่ดีที่สุดที่เรียกว่า Callable ใช้ NumPy 1D-array เป็นอาร์กิวเมนต์

• available_predictors_values : int ลำดับรายการของค่าที่มีอยู่สำหรับแต่ละตัวทำนาย (แต่ละมิติของอาร์กิวเมนต์)

• random_counts_by_predictors : Int หรือ Int Sequence ตัวเลือกควรใช้ตัวเลือกแบบสุ่มกี่ตัวเลือกสำหรับแต่ละตัวแปร? ใช้รายการ/อาร์เรย์ numpy สำหรับตัวเลือกที่เลือกสำหรับแต่ละตัวทำนาย (หรือ int - หมายเลขหนึ่งสำหรับแต่ละตัวทำนาย) ค่าเริ่มต้นคือ 3

• greedy_step : int, ตัวเลือกทางเลือกที่ดีกว่าทางออกที่ดีกว่าหลังจากปีนเขาโดยตัวทำนาย Greedy_step ค่าเริ่มต้นคือ 1

• start_solution : ไม่มีหรือลำดับ int, จุดเสริมเมื่ออัลกอริทึมเริ่มต้น ค่าเริ่มต้นคือไม่มี - โซลูชันการเริ่มต้นแบบสุ่ม

• max_function_evals : INT, การประเมินค่าสูงสุดของฟังก์ชั่นเพิ่มเติม ค่าเริ่มต้นคือ 1,000

• maximize : บูลเสริมฟังก์ชั่นให้สูงสุด? (ลดลงโดยค่าเริ่มต้น) ค่าเริ่มต้นเป็นเท็จ

• seed : int หรือไม่มีเลย สุ่มเมล็ด (ไม่มีถ้าไม่สำคัญ) ค่าเริ่มต้นคือไม่มี

ผลตอบแทน : Tuple มีวิธีแก้ปัญหาที่ดีที่สุดและค่าฟังก์ชั่นที่ดีที่สุด

ตัวอย่าง

จำนวนการค้นหาแบบสุ่มของตัวเอง

คุณสามารถตั้งค่าค่า random_counts_by_predictors แตกต่างกันของคุณค่าที่แตกต่างกันของคุณค่าสำหรับตัวทำนายแต่ละตัว ตัวอย่างเช่นหากชุดทำนายที่มีอยู่มีค่าเพียง 3-5 ค่าจะดีกว่าที่จะตรวจสอบทั้งหมด แต่ถ้ามี 100+ ค่าจะเป็นการดีกว่าที่จะตรวจสอบ 20-40 ของพวกเขาไม่ใช่ 5 ดูตัวอย่าง:

 import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descent


def func ( array ):
    return ( np . sum ( array ) + np . sum ( array ** 2 )) / ( 1 + array [ 0 ] * array [ 1 ])


available_predictors_values = [
    np . array ([ 10 , 20 , 35 , 50 ]),
    np . array ([ - 5 , 3 , - 43 , 0 , 80 ]),
    np . arange ( 40 , 500 ),
    np . linspace ( 1 , 100 , num = 70 ),
    np . array ([ 65 , 32 , 112 ]),
    np . array ([ 1 , 2 , 3 , 0 , 9 , 8 ]),
    np . array ([ 1 , 11 , 111 , 123 , 43 ]),
    np . array ([ 8 , 9 , 0 , 5 , 4 , 3 ]),
    np . array ([ - 1000 , - 500 , 500 , 1000 ])
]


solution , value = Hill_Climbing_descent ( function = func ,
    available_predictors_values = available_predictors_values ,
    random_counts_by_predictors = [ 4 , 5 , 2 , 20 , 20 , 3 , 6 , 6 , 4 ],
    greedy_step = 1 ,
    start_solution = None ,
    max_function_evals = 1000 ,
    maximize = False ,
    seed = 1 )

print ( solution )
print ( value )

# [  10.   -5.  494.  100.  112.    9.  123.    9. 1000.]
# -26200.979591836734

ขั้นตอนโลภที่แตกต่างกัน

พารามิเตอร์ greedy_step มีความสำคัญในบางงาน มันจะดีกว่าที่จะใช้ greedy_step = 2 หรือ greedy_step = 3 แทนที่จะเป็น greedy_step = 1 และไม่ใช่ทางเลือกที่ดีที่จะใช้ Big greedy_step หากเราไม่สามารถประเมินฟังก์ชั่นที่ดีที่สุดได้หลายครั้ง

 import numpy as np
from DiscreteHillClimbing import Hill_Climbing_descent


def func ( array ):
    return ( np . sum ( array ) + np . sum ( np . abs ( array ))) / ( 1 + array [ 0 ] * array [ 1 ]) - array [ 3 ] * array [ 4 ] * ( 25 - array [ 5 ])


available_predictors_values = [
    np . array ([ 10 , 20 , 35 , 50 ]),
    np . array ([ - 5 , 3 , - 43 , 0 , 80 ]),
    np . arange ( 40 , 500 ),
    np . linspace ( 1 , 100 , num = 70 ),
    np . array ([ 65 , 32 , 112 ]),
    np . array ([ 1 , 2 , 3 , 0 , 9 , 8 ]),
    np . array ([ 1 , 11 , 111 , 123 , 43 ]),
    np . array ([ 8 , 9 , 0 , 5 , 4 , 3 ]),
    np . array ([ - 1000 , - 500 , 500 , 1000 ])
]


seeds = np . arange ( 100 )

greedys = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]

results = np . empty ( len ( greedys ))

for i , g in enumerate ( greedys ):
    vals = []
    for s in seeds :
        _ , value = Hill_Climbing_descent ( function = func ,
            available_predictors_values = available_predictors_values ,
            random_counts_by_predictors = [ 4 , 5 , 2 , 20 , 20 , 3 , 6 , 6 , 4 ],
            greedy_step = g ,
            start_solution = [ v [ 0 ] for v in available_predictors_values ],
            max_function_evals = 100 ,
            maximize = True ,
            seed = s )
        vals . append ( value )
    
    results [ i ] = np . mean ( vals )

import pandas as pd

print ( pd . DataFrame ({ 'greedy_step' : greedys , 'result' : results }). sort_values ([ 'result' ], ascending = False ))

#    greedy_step       result
# 1            2  1634.172483
# 0            1  1571.038514
# 2            3  1424.222610
# 3            4  1320.051325
# 4            5  1073.783527
# 5            6   847.873058
# 6            7   362.113555
# 7            8    24.729801
# 8            9  -114.200000