查看: 2658|回复: 0

爬山算法

字体大小: 正常放大

1198 主题	4 听众	2978 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

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

步骤 1: 定义目标函数

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

function y = myFunction(x)5 b# b6 m( w$ y* Y\\" ]# ^# w
y = -x^2 + 4*x;% D( \7 [% d( d M& r x' N4 m
end

步骤 2: 实现爬山算法

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

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)
! B% i0 e0 _, Q% L
currentX = initialX;
' i* a' k0 g; z- E4 A
currentY = func(currentX);; L$ D M8 F2 }5 ~
for i = 1:numIterations( o6 p: K1 ], n. ~
% 尝试在两个方向上移动7 E, _1 N8 c. m
newX = [currentX + stepSize, currentX - stepSize];. l* E2 k$ I0 e0 A4 q6 c
newY = [func(newX(1)), func(newX(2))];, {: ]. v$ p/ \; V\\" a
# ]1 j0 _- ?9 n: b8 {+ c
% 找出最好的移动方向
! I$ u4 ]- A6 ]+ z N& H* K
[maxY, idx] = max(newY);
! Q, X4 J8 F. v
( d+ c7 a5 b6 S3 w7 g+ W) l
% 如果找到了更好的解，则更新当前解, ~3 L8 b- t0 ]& C5 R, f
if maxY > currentY' |- z8 L/ c( U+ T D+ w0 @
currentX = newX(idx);- m\\" _, c. D% B& W; L( q5 D
currentY = maxY;
! H7 c- f! m3 r! T P
else( D3 s3 Z+ O6 T( x3 ^1 y
% 如果没有更好的解，结束搜索
( C) m* b+ E+ g5 a5 @0 j6 l0 z
break;
9 L6 l- V0 u\\" J
end, j\\" [- |( L% G& @* J$ W/ y
end9 Y8 T3 t) T# h o5 g; D
bestX = currentX;
. I/ R+ k0 `1 u9 h# W* M8 a
bestY = currentY;/ j/ I* B/ U1 p
end
+ U) R' g/ |5 L6 N4 {9 R4 o3 a
1 G. \& t3 j. D+ C
% 运行爬山算法
% X& A# f! J5 b7 @) e
initialX = 0; % 初始点
& n G3 _9 ^: O
stepSize = 0.1; % 步长% C5 Y6 I( |2 V6 n! f4 R
numIterations = 100; % 迭代次数) V5 V; D- G( X b+ f) }
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations) 
! B% i0 e0 _, Q% L
    currentX = initialX; 
' i* a' k0 g; z- E4 A
    currentY = func(currentX);; L$ D  M8 F2 }5 ~

for i = 1:numIterations( o6 p: K1 ], n. ~

% 尝试在两个方向上移动7 E, _1 N8 c. m

newX = [currentX + stepSize, currentX - stepSize];. l* E2 k$ I0 e0 A4 q6 c

newY = [func(newX(1)), func(newX(2))];, {: ]. v$ p/ \; V\\" a

# ]1 j0 _- ?9 n: b8 {+ c

% 找出最好的移动方向 
! I$ u4 ]- A6 ]+ z  N& H* K
        [maxY, idx] = max(newY); 
! Q, X4 J8 F. v
         
( d+ c7 a5 b6 S3 w7 g+ W) l
        % 如果找到了更好的解，则更新当前解, ~3 L8 b- t0 ]& C5 R, f

if maxY > currentY' |- z8 L/ c( U+ T  D+ w0 @

currentX = newX(idx);- m\\" _, c. D% B& W; L( q5 D

currentY = maxY; 
! H7 c- f! m3 r! T  P
        else( D3 s3 Z+ O6 T( x3 ^1 y

% 如果没有更好的解，结束搜索 
( C) m* b+ E+ g5 a5 @0 j6 l0 z
            break; 
9 L6 l- V0 u\\" J
        end, j\\" [- |( L% G& @* J$ W/ y

end9 Y8 T3 t) T# h  o5 g; D

bestX = currentX; 
. I/ R+ k0 `1 u9 h# W* M8 a
    bestY = currentY;/ j/ I* B/ U1 p

end 
+ U) R' g/ |5 L6 N4 {9 R4 o3 a
 
1 G. \& t3 j. D+ C
% 运行爬山算法 
% X& A# f! J5 b7 @) e
initialX = 0; % 初始点 
& n  G3 _9 ^: O
stepSize = 0.1; % 步长% C5 Y6 I( |2 V6 n! f4 R

numIterations = 100; % 迭代次数) V5 V; D- G( X  b+ f) }

[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);: c; L7 v8 F4 V% u3 w: L5 M
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

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