DiscreteHillClimbing

تسلق التل المنفصل

توفر هذه الحزمة (من DPEA) تنفيذ خوارزمية تسلق التل للمهام المنفصلة.

 pip install DiscreteHillClimbing

• تسلق التل المنفصل
  • عن
  • لماذا تسلق التل؟
  • رمز كاذب
  • عملية العمل
  • حدود
  • أمثلة
    • تهم البحث العشوائي
    • خطوات جشع مختلفة

عن

يعد تسلق التل ( التقليل من الإحداثيات ) هو الخوارزمية الأكثر بساطة للمهام المنفصلة كثيرًا (واحد أبسط يحصل على أفضل ما في الأمر بشكل عشوائي تمامًا). في المهام المنفصلة ، يمكن أن يكون لكل مؤلف قيمة من مجموعة محدودة ، وبالتالي يمكننا التحقق من جميع قيم المتنبئ (متغير) أو جزء عشوائي صغير منه والقيام بالتحسين بواسطة مؤشر واحد. بعد ذلك يمكننا التحسين من خلال تنبؤ آخر وهلم جرا. كما يمكننا أن نحاول العثور على حل أفضل باستخدام 1 و 2 و 3 و ... المتنبئين واختيار أفضل تكوين فقط.

هناك مجموعة متنوعة للغاية من الطرق لتحقيق تسلق التل ، لذلك حاولت أن أجعل تطبيقًا بسيطًا وعالميًا. بالتأكيد ، قد يكون من الأفضل إنشاء تطبيقك (أسرع) على مهمتك الخاصة ، ولكن هذه الحزمة هي خيار مرن جيد للبدء.

لماذا تسلق التل؟

تسلق التل هو خط الأساس المثالي عندما تبدأ في البحث عن الحل. إنه يساعد حقًا ويمكنه حقًا الحصول على نتيجة جيدة جدًا باستخدام تقييمات وظائف 50-200 فقط.

رمز كاذب

انظر الفكرة الرئيسية لتنفيذي في هذا الرمز الكاذب:

 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 ؛ تستخدم الدالة المحسّنة القابلة للتطبيق Numpy 1D Array كوسيطة.

• available_predictors_values : تسلسل int قائمة بالقيم المتاحة لكل تنبؤ (كل خافت للسيجة).

• random_counts_by_predictors : تسلسل int أو int ، كم عدد الخيارات العشوائية التي يجب أن تستخدمها لكل متغير؟ استخدم قائمة القائمة/numpy لخيار تحديد كل تنبؤ (أو int - رقم واحد لكل تنبؤ). الافتراضي هو 3.

• greedy_step : int ، اختيارات تكنولوجيا المعلومات الاختيارية حل أفضل بعد التسلق بواسطة تنبؤات الجشع. الافتراضي هو 1.

• start_solution : لا شيء أو تسلسل int ، نقطة اختيارية عند بدء الخوارزمية. الافتراضي هو لا شيء - حل بداية عشوائية

• max_function_evals : int ، عدد الأقصى الاختياري لتقييمات الوظائف. الافتراضي هو 1000.

• maximize : Bool ، اختياري تعظيم الوظيفة؟ (تقليل التقليل افتراضيًا). الافتراضي خاطئ.

• 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