一般フォーラム

コメントがつかないので，あまりよくわかっていない人ですが，適当に書きます．

幅の調整は，フロート環境であることを放棄してよいならば，H オプションをつけておけば
minipage に入れることで調整できそうです．

\documentclass{article}
\usepackage[ruled]{algorithm2e}
\begin{document}
\begin{center}
  \begin{minipage}{.5\textwidth}
    \begin{algorithm}[H]
      $a \leftarrow b$
      \caption{Substitution}
    \end{algorithm}
  \end{minipage}
\end{center}
\end{document}

フロート環境であることを保ちたい場合や，いちいち minipage に入れるのが面倒な場合は，
内部のマクロに細工をしておくか，\begin{algorithm}[H]...\end{algorithm} を含む
新しいフロート環境を定義するかになると思います．
以下は前者の例です（center 環境を入れて，全体を中央寄せにしています）．

\documentclass{article}
\usepackage[ruled]{algorithm2e}
\newdimen\algorithmwidth
\setlength{\algorithmwidth}{.5\textwidth} % 幅の指定
\makeatletter
\edef\@algocf@start{\unexpanded{%
    \begin{center}
      \begin{minipage}{\algorithmwidth}
  }\expandafter\unexpanded\expandafter{\@algocf@start}}
\expandafter\def\expandafter\@algocf@finish\expandafter{\@algocf@finish
      \end{minipage}
    \end{center}
}
\makeatother
\begin{document}
Algorithm~\ref{alg:subst} is a simple substitution.
\begin{algorithm}[t]
  $a \leftarrow b$
  \caption{Substitution}
  \label{alg:subst}
\end{algorithm}
\end{document}

Stack Exchange にも同じような質問があります．
http://tex.stackexchange.com/questions/23296/setting-caption-rule-width-in-algorithm2e-algs
http://tex.stackexchange.com/questions/7484/set-width-of-algorithm-environment-preferably-document-wide