Caching is a technique first used by memory management to reduce bus traffic and latency of data access. Web traffic has increased tremendously since the beginning of the 1990s. With the significant increase of web traffic, caching techniques are applied to web caching to reduce network traffic, user-perceived latency, and server load by caching the documents in local proxies. In this paper, we analyzed both advantages and disadvantages of some current web cache replacement algorithms including lowest relative value algorithm, least weighted usage algorithm and Least Unified-Value (LUV) algorithm. Based on our analysis, we proposed a new algorithm, called least Grade Replacement (LGR), which takes recency, frequency, perfect-history, and document size into account for web cache optimization. The optimal recency coefficients were determined by using 2and 4-way set associative caches. The cache size was varied from 32k to 256k in the simulation. The simulation results showed that the new algorithm (LGR) is better than LRU and LFU in terms of Hit Ratio (HR) and Byte Hit Ratio (BHR).