查看: 2581|回复: 0

爬山算法

字体大小: 正常放大

1192 主题	4 听众	2946 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

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

步骤 1: 定义目标函数

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

function y = myFunction(x)
8 F\\" |2 P\\" x# J5 a3 t* _* S
y = -x^2 + 4*x;3 ]2 R% f1 F9 v
end

步骤 2: 实现爬山算法

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

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations)
, F) z/ z\\" `# r$ S$ t
currentX = initialX; a+ W; `1 Q) n R- T
currentY = func(currentX);
: I+ f2 F\\" g* C
for i = 1:numIterations
8 b* e8 g8 t! ]* U4 V. v
% 尝试在两个方向上移动, Z4 z5 ^\\" t- | g T/ g3 p- P+ Q
newX = [currentX + stepSize, currentX - stepSize];
$ L: \8 P/ }1 ~# N V
newY = [func(newX(1)), func(newX(2))];5 `; _- {+ H# V1 K! Z: P
4 D# |- d* o6 A8 B
% 找出最好的移动方向 F- e' \. s- W L
[maxY, idx] = max(newY);
3 T# N. h7 f+ j0 \ l3 c
$ b5 d: Y9 x( B\\" K3 \
% 如果找到了更好的解，则更新当前解7 p1 X* v! Z+ S* y
if maxY > currentY( J/ Y& R+ Q+ U7 a+ T- i\\" A\\" s. Z) i
currentX = newX(idx);- I1 [& e9 Q f- L
currentY = maxY;: I8 e# X0 ^1 Y\\" H, R5 B+ a: x9 K$ w( E
else( x6 F6 b- s7 L5 I
% 如果没有更好的解，结束搜索
( |; T5 }5 t. @: z( z1 w
break;2 F4 g: K; Z! y7 e/ ^% ?4 l
end2 D' U+ G6 k9 V: j0 R4 y
end
\\" b0 E: k. K9 i9 h0 n% T
bestX = currentX;
bestY = currentY;
9 M, D6 s$ ]1 t/ h$ G$ {3 ] q
end
2 O3 M# k3 v: S
# S8 D3 |$ H2 L0 x: {
% 运行爬山算法
7 d) {6 n& _5 O% d\\" O: A
initialX = 0; % 初始点+ {# `/ [1 X f) u
stepSize = 0.1; % 步长7 Z0 k$ b Z$ E; W. v; Q5 l
numIterations = 100; % 迭代次数
$ U- ?' m4 q5 J0 |( A
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

function [bestX, bestY] = hillClimbing(func, initialX, stepSize, numIterations) 
, F) z/ z\\" `# r$ S$ t
    currentX = initialX;  a+ W; `1 Q) n  R- T

currentY = func(currentX); 
: I+ f2 F\\" g* C
    for i = 1:numIterations 
8 b* e8 g8 t! ]* U4 V. v
        % 尝试在两个方向上移动, Z4 z5 ^\\" t- |  g  T/ g3 p- P+ Q

newX = [currentX + stepSize, currentX - stepSize]; 
$ L: \8 P/ }1 ~# N  V
        newY = [func(newX(1)), func(newX(2))];5 `; _- {+ H# V1 K! Z: P

4 D# |- d* o6 A8 B

% 找出最好的移动方向  F- e' \. s- W  L

[maxY, idx] = max(newY); 
3 T# N. h7 f+ j0 \  l3 c
        $ b5 d: Y9 x( B\\" K3 \

% 如果找到了更好的解，则更新当前解7 p1 X* v! Z+ S* y

if maxY > currentY( J/ Y& R+ Q+ U7 a+ T- i\\" A\\" s. Z) i

currentX = newX(idx);- I1 [& e9 Q  f- L

currentY = maxY;: I8 e# X0 ^1 Y\\" H, R5 B+ a: x9 K$ w( E

else( x6 F6 b- s7 L5 I

% 如果没有更好的解，结束搜索 
( |; T5 }5 t. @: z( z1 w
            break;2 F4 g: K; Z! y7 e/ ^% ?4 l

end2 D' U+ G6 k9 V: j0 R4 y

end 
\\" b0 E: k. K9 i9 h0 n% T
    bestX = currentX; 
8 p; I- L+ U8 K- S7 E8 p9 H- W% o* N( @# Q
    bestY = currentY; 
9 M, D6 s$ ]1 t/ h$ G$ {3 ]  q
end 
2 O3 M# k3 v: S
 
# S8 D3 |$ H2 L0 x: {
% 运行爬山算法 
7 d) {6 n& _5 O% d\\" O: A
initialX = 0; % 初始点+ {# `/ [1 X  f) u

stepSize = 0.1; % 步长7 Z0 k$ b  Z$ E; W. v; Q5 l

numIterations = 100; % 迭代次数 
$ U- ?' m4 q5 J0 |( A
[bestX, bestY] = hillClimbing(@myFunction, initialX, stepSize, numIterations);

步骤 3: 输出结果

展示算法找到的最优解。

disp(['The maximum value of f(x) is found at x = ', num2str(bestX)]);4 l, z% I9 c9 V _0 i1 @/ }' y
disp(['The maximum value of f(x) is ', num2str(bestY)]);

复制代码

步骤 4: 可视化

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

x = 0:0.01:5;
, f: `* j\\" e, F6 t
y = myFunction(x);# z5 @8 M8 {8 Q$ D0 H: P6 D: t2 T- k
figure;: G& c/ p* ^- L C' N. S: w# S
plot(x, y, 'b-', bestX, bestY, 'ro');7 J' b* ?) E8 r. G8 p
title('Function Optimization using Hill Climbing');, n4 s2 u' T) s# I( m% E, |( L
xlabel('x');8 B& |7 E! D+ n! y2 u* L
ylabel('f(x)');& B& ~- M' }1 T8 Y
legend('Function', 'Maximum Point');