查看: 2583|回复: 0

爬山算法

字体大小: 正常放大

1192 主题	4 听众	2946 积分

该用户从未签到

电梯直达

1^#

发表于 2024-4-26 15:44 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

使用爬山算法优化简单的数学函数

假设我们需要找到函数 𝑓(𝑥)=−𝑥^2+4𝑥的最大值。这是一个具有单个局部最大值的简单抛物线函数。

步骤 1: 定义目标函数

首先，定义我们需要优化的函数。在MATLAB中，我们可以创建一个函数来计算给定x值的 𝑓(𝑥)。

function y = myFunction(x)) X/ b- Z: f b, S\\" w1 T9 t
y = -x^2 + 4*x;. V2 i. H3 m! f: W# H) {
end

步骤 2: 实现爬山算法

接着，实现爬山算法。我们从一个随机点开始，然后在每一步尝试移动到一个“邻居”点，如果那里的值更高，就移动到那里。

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)
% _4 Y! L& m. N2 T# d* W1 Y6 n* s
currentX = initialX;
; O/ h% D6 S/ [9 |# x- i
currentY = func(currentX);
/ x% H) l% w' K& S }! l
for i = 1:numIterations
* K8 Y @4 J/ x6 r$ m\\" t% o9 s
% 尝试在两个方向上移动
J, v2 J4 J' {/ a9 c
newX = [currentX + stepSize, currentX - stepSize];
7 \- j- k/ R. o6 C4 P& S
newY = [func(newX(1)), func(newX(2))];
) q/ v ?4 c5 v6 q9 |% N( E
6 j- I& a3 F& |
% 找出最好的移动方向
' Q7 E, E, W/ J/ F9 z
[maxY, idx] = max(newY);* t; O\\" i& a2 K2 z& p3 F/ ^. d2 |
9 K3 Y3 P6 V _, T' m
% 如果找到了更好的解，则更新当前解
$ U6 `* a1 A4 ?# ? z2 q& x# h5 O
if maxY > currentY3 M. C& O6 ~, c' a- X- c, E- D
currentX = newX(idx);
4 t4 V7 S. j P, p3 W4 z' @
currentY = maxY;5 z6 a ~/ e) h0 `
else: a' E7 f( F0 n7 d. o& o- Q
% 如果没有更好的解，结束搜索- \' q( A; {, g8 k s+ |
break;
@( X: J+ ~* z6 h ^
end
/ \$ X; ~4 k% O! O% [& U
end
! H) `) G( h$ \5 G
bestX = currentX;
& B% p- p' j; H7 v8 `/ s# N& r
bestY = currentY;
9 S0 H5 h$ w$ }& m4 H7 |
end- \ [/ m# Q! p2 b& ^
/ T& @& J% x, L2 L% R( M
% 运行爬山算法
# n( \+ z- F) d) v: Q8 d
initialX = 0; % 初始点; w6 t& _- Y, K2 t3 h4 D
stepSize = 0.1; % 步长 C- ?7 _ t! q' S
numIterations = 100; % 迭代次数
$ d: t4 ]5 x& \) b6 c# {
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations) 
% _4 Y! L& m. N2 T# d* W1 Y6 n* s
    currentX = initialX; 
; O/ h% D6 S/ [9 |# x- i
    currentY = func(currentX); 
/ x% H) l% w' K& S  }! l
    for i = 1:numIterations 
* K8 Y  @4 J/ x6 r$ m\\" t% o9 s
        % 尝试在两个方向上移动 
  J, v2 J4 J' {/ a9 c
        newX = [currentX + stepSize, currentX - stepSize]; 
7 \- j- k/ R. o6 C4 P& S
        newY = [func(newX(1)), func(newX(2))]; 
) q/ v  ?4 c5 v6 q9 |% N( E
 
6 j- I& a3 F& |
        % 找出最好的移动方向 
' Q7 E, E, W/ J/ F9 z
        [maxY, idx] = max(newY);* t; O\\" i& a2 K2 z& p3 F/ ^. d2 |

9 K3 Y3 P6 V  _, T' m
        % 如果找到了更好的解，则更新当前解 
$ U6 `* a1 A4 ?# ?  z2 q& x# h5 O
        if maxY > currentY3 M. C& O6 ~, c' a- X- c, E- D

currentX = newX(idx); 
4 t4 V7 S. j  P, p3 W4 z' @
            currentY = maxY;5 z6 a  ~/ e) h0 `

else: a' E7 f( F0 n7 d. o& o- Q

% 如果没有更好的解，结束搜索- \' q( A; {, g8 k  s+ |

break; 
  @( X: J+ ~* z6 h  ^
        end 
/ \$ X; ~4 k% O! O% [& U
    end 
! H) `) G( h$ \5 G
    bestX = currentX; 
& B% p- p' j; H7 v8 `/ s# N& r
    bestY = currentY; 
9 S0 H5 h$ w$ }& m4 H7 |
end- \  [/ m# Q! p2 b& ^

/ T& @& J% x, L2 L% R( M
% 运行爬山算法 
# n( \+ z- F) d) v: Q8 d
initialX = 0; % 初始点; w6 t& _- Y, K2 t3 h4 D

stepSize = 0.1; % 步长  C- ?7 _  t! q' S

numIterations = 100; % 迭代次数 
$ d: t4 ]5 x& \) b6 c# {
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);
2 U+ s; r2 g) w) i\" s+ `3 y g; o
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

可视化函数和算法找到的最大值点，以更好地理解算法的行为。

x = 0:0.01:5;$ _$ n\\" k( q4 c\\" H( ]# q
y = myFunction(x);) `3 ?* }6 z\\" o {3 |
figure;
5 ?( w( S# {0 L! b
plot(x, y, 'b-', bestX, bestY, 'ro');
' { x. b S9 @) M
title('Function Optimization using Hill Climbing');. G* ?& ~+ b3 H# N\\" k7 Y\\" u# z
xlabel('x');; D3 o4 b5 x8 m+ b# i. E
ylabel('f(x)');) V5 X9 q6 z3 e& u3 m% l
legend('Function', 'Maximum Point');